Google Kickstart 2019 Round C

소스 코드 위치: Google Kickstart 2019 Round C

 

A. Wiggle Walk

  A 치고 너무 복잡하게 푼 느낌이 든다..

  행과 열에 대해서 DSU를 따로 관리한다. 다음에 이동하는 위치가 (ny, nx)라면 인접한 4방향에 대해서 이미 방문한 칸이 있다면 merge해준다. 이 때 DSU에서 관리하는 데이터는 left와 right로 두 변수가 있고, 각각 행 또는 열에서 이미 방문한 칸들에 가장 가까운 작은 값과 큰 값을 말한다.

  위와 같이 행과 열 각각 DSU를 관리하면서 상하좌우 이동해주면 된다.

 

B. Circuit Board

  i번째 행 j번째 열을 구성하고자하는 사각형의 우측 하단 꼭지점에 위치한다고 치자. i행만 쓴다면 i행에서 최대값과 최소값의 차이가 K를 넘어서지 않는 좌표가 있고, 거기서 j열까지의 거리가 w1였다고 하자. 여기서 만들 수 있는 사각형의 최대 크기는 1 x w1이다. 다음으로 i-1번째 행까지 포함하여 i-1, i를 사용하여 사각형을 구성할 때, 마찬가지로 (i-1,j)를 포함하여 i-1행에서 최대값과 최소값의 차이가 K를 넘어서지 않는 좌표가 있고, 거기서 j열까지의 거리가 w2라고하자. 그러면 만들 수 있는 사각형의 최대 크기는 2 x min(w1, w2)가 된다. 이렇게 위로 올라가면서 최대값을 계산해주자.

 

[최대값과 최소값을 K이하로 하는 좌표 찾기]

  map을 적절히 사용하여 투포인터를 이용하면 구현할 수 있다. c++ 상 map은 정렬된 키로 관리하기 때문에 이 특성을 이용하여 현재 V[i, j]에 해당하는 값과 K 초과 차이가 발생하는 모든 열 인덱스를 삭제하고, 삭제된 값 중 가장 큰 값에서 하나 오른쪽으로 이동한 인덱스가 바로 그 좌표가 된다.

 

C. Catch Some

  관찰 포인트가 몇 가지 있다.

  1. 입을 셔츠의 색을 결정하고 일단 한 번 강아지들을 방문(observe)하고 나면 이 셔츠의 색을 다시 입을 필요가 없다.

  명백하게도 다시 입는 과정은 그만큼 방문하는 것은 손해다.

  2. 각 셔츠의 색을 방문하는 과정은 독립적이다. 즉, 색에 대한 순서는 결과에 상관없다.

  3. 마지막에 입는 셔츠의 색에 대해서만 강아지들을 방문하고 나서 집에 돌아올 필요가 없다. 즉, 색 중 단 하나만 집으로 돌아올 필요가 없다.

  이를 토대로 상태를 정의한다.

dp[color][k][flag] = color 색에 대해서 k마리의 강아지를 방문해야하고, flag가 1이면 이미 마지막에 입을 색이 결정됐음을, 0이라면 마지막에 입을 색이 결정되지 않았음을 말한다.

  위처럼 상태를 정의하면 나머지 부분은 다이나믹 프로그래밍으로 진행하면 된다.