[ICPC 본선 대비 뇌셋] Day 1

백준 16710 Dragging www.acmicpc.net/problem/16710

16710번: Dragging

난이도를 안보고 푸는 연습을 하면 좋을 것 같으므로, 당분간 솔브닥을 끄고 문제를 푼다.

풀이는 뇌에서 생각한 경로 -> 남을 위한 설명 -> (필요하다면)코딩을 위한 설명 순으로 전개할 예정.

 

[풀이]

1차원 배열로 생각해보았으나 충분히 쉽지 않아 다음과 같이 문제를 쉽게 했다. (처음에는 k = 1인 상황을 생각했다.)

1. 태영이가 k번 끌고간다.

2. 승한이가 k번 끌고간다.

 

[관찰 1] 태영이가 어디로 가던지 승한이는 제자리로 돌아올 수 있다.

원점에서 시작했다고 할 때, 태영이가 i번 (-k <= i <= k)으로 이동하면, 승한이는 j번(i-k<=j<=i+k)으로 갈 수 있다.

B[i]를 i번에서 갈 수 있는 가장 작은 염도라고 정의하자. 즉, 

B[i] = min(A[j] : i-k<=j<=i+k)

그러면 태영이가 idx = argmax(B[i], -k <= i <= k)로 가는 경우가 최선일 것 같으며, B[idx]가 강력한 답의 후보임을 떠올릴 수 있다.

[증명]

1) ans >= B[idx]

태영이가 idx로 이동했다고 가정하자.

승한이가 B[idx]의 음식이 있는 곳으로 이동하지 않고 j로 이동하였다면, abs(j-idx)<=k이므로 B[idx]보다 짜거나 같은 음식을 먹는다.

다음 턴에도 태영이는 idx로 이동할 수 있고, 무조건 B[idx]보다 짜거나 같은 음식을 먹으므로 답은 B[idx]보다 크거나 같다.

 

2) ans <= B[idx]

태영이가 idx로 이동하지 않았고, j로 이동했다고 가정하자.

승한이는 B[j]<=B[idx]이므로, 이 경우 염도가 B[j]인 곳으로 이동할 수 있다.

턴이 지나도 승한이는 제자리로 돌아올 수 있으므로, 승한이는 최종적으로 B[j] <= B[idx]보다 염도가 낮거나 같은 음식을 먹을 수 있다.

 

위의 논리를 보면 단 한 턴만에 정답이 결정됨을 알 수 있다. idx를 새로운 원점에 대해서 새로 정의하면 점점 답이 커질것 같지만 그렇지 않음은 쉽게 확인할 수 있다.

 

한편 문제에서는 배열이 아닌 그래프에서 태영 2칸 -> 승한 1칸 -> 태영 1칸 -> 승한 2칸 순으로 움직이지만. 거의 똑같은 논리를 적용시킬 수 있다.

B[i] = min(A[j] : dist(i, j)<=2)

idx = argmax(B[i] : dist(0, i) <= 2)

로 정의하면, 태영이가 idx로 가고, 승한이가 한칸 움직이면 반대방향으로 간다. 그리고 승한이는 B[idx]인 위치로 이동하면 된다.

원점에서 거리가 3일 때 B의 값이 B[idx]보다 크다면 한가지 문제점이 생긴다. 처음 태영이가 거리 2인 위치로 움직였을 때, 승한이가 가만히 있다면 태영이가 B[idx]가 큰 곳으로 이동할 수 있기 때문이다.

하지만 승한이가 무조건 원점에서 거리 1인 곳으로 이동할 수 있기 때문에 문제가 사라진다.

 

[코딩]

각 점에서 거리 2 안의 최솟값을 찾는 문제로 귀결된다. 그냥 찾으면 M^2이므로, 각 점 i에서 거리 1 안에 있는 음식의 염도의 최솟값 C[i]를 찾고, 다시 각 점 i에서 거리 1 안에 있는 C[i]의 최솟값을 찾는 식으로 진행하면 O(M)에 찾을 수 있다.

 

[복잡도] O(M+N)

 

한번도 풀이를 정돈해본적이 없어서 짧은 글임에도 1시간 정도가 걸렸는데 꽤 힘들었다. 앞으로 연습하면 나아지겠지?