Sightseeing in Kyoto 힌트와 풀이

이 글에서는 BOJ 24943 Sightseeing in Kyoto의 풀이를 다룬다. 총 17단계의 힌트에 걸쳐서 풀이를 제공할 것이며 풀다가 막힐 때 이 글을 한 문단씩 읽으면 된다!

참고로 이 글은 내가 이 문제를 풀 당시의 사고 흐름을 거의 그대로 가져왔다. 그럼 바로 시작하자.

스포일러 방지를 위한 박스이다. 힌트 1을 보려면 스크롤하자.
힌트들은 가림 없이 쓰여 있다.
실수로 다음 힌트까지 스크롤하는 것을 방지하기 위해
각 힌트 아래에 작은 박스를 붙여 두긴 했으나,
그렇게 크지는 않으므로 천천히 조심스럽게 스크롤하는 것을 권장한다.

힌트 1

정수끼리의 연산이 상수 시간에 일어난다고 가정했을 때, 총 \(O(N+M)\) 시간에 풀 수 있다. 이를 통해 꽤 많은 알고리즘이 배제될 것이다.

힌트 2를 보려면 스크롤하자.

힌트 2

가로 방향 길 중, 그리고 세로 방향 길 중 가중치가 가장 작은 길이 꽤 중요한 역할을 할 것이라는 것은 짐작이 갈 것이다. 이 길에 주목해 보자. 이 길 때문에 당신의 경로는 어떤 영향을 받는가?

힌트 3을 보려면 스크롤하자.

힌트 3

이미 보지 않았다면, 이 문제의 태그는 #그리디 알고리즘 #기하학 #볼록 껍질이다.

단, 이들 중 #기하학 태그는 #볼록 껍질 때문에 종속 관계상 자동으로 붙은 태그이다. 따라서 사실상 나머지 #그리디 알고리즘 #볼록 껍질 태그의 문제라고 보면 된다.

힌트 4를 보려면 스크롤하자.

힌트 4

가로 방향 길들 중 가장 가중치가 작은 길을 \(L\)이라 하자. \(L\) 위에서 최대한 오래 보내고 싶은 경향은 당연히 존재한다. 처음에는 \(L\)보다 위쪽에서 시작하며, \(L\)까지 도달해야 한다. 빠르게 \(L\)에 도달하고 싶다면, 세로 방향 길을 많이 이용해야 할 것이고 가로 방향 길은 많이 이용하고 싶지 않을 것이다. 그럼에도 불구하고 가로 방향 길을 이용한다면, 그것은 무엇 때문일까?

힌트 5를 보려면 스크롤하자.

힌트 5

힌트 4에 대한 답: 현재 사용하고 있는 세로 방향 길보다 가중치가 작은 세로 길로 옮겨 가기 위해서. 만약 현재 위치한 가로 방향 길의 가중치가 충분히 낮다면, 그런 선택을 할 수 있을 것이다. 또한 당연하겠지만 이 논증은 가로와 세로의 역할을 바꾸어도 똑같이 적용된다.

힌트 6을 보려면 스크롤하자.

힌트 6

\(L\)보다 위에 있는 시점을 가정하자. 만약 현재 위치한 세로 방향 길보다 조금 더 오른쪽에 위치한 세로 방향 길의 가중치가 더 낮다면, 가로 방향 길을 타고 오른쪽으로 이동하고 싶을 것이다. 이 때 두 가지 고민거리가 발생한다. 첫 번째는 최대한 빨리 옮겨 가서 낮은 가중치를 조금이나마 더 누리는 것, 두 번째는 옮겨 갈 때 낮은 가중치의 가로 방향 길이 나올 때까지 기다리는 것이다.

다시 말해 \(L\)보다 위에 있는 가로 방향 길의 경쟁력(?)은 두 가지에 의해 결정된다. 첫 번째는 위에 있을수록 더 쓸만하고, 두 번째는 가중치가 낮을수록 더 쓸만하다.

힌트 7을 보려면 스크롤하자.

힌트 7

힌트 6에서 언급한 두 가지의 경쟁력(?)을 기반으로 판단할 때, ‘전혀 쓸 이유가 없는 도로’는 무엇인지 생각해 보자. 또는 다른 말로 해서, ‘쓸 이유가 조금이라도 있는 도로’들을 모아 놓으면 어떻게 되는지 살펴보자.

힌트 8을 보려면 스크롤하자.

힌트 8

힌트 7에 대한 답: \(L\)보다 위에 있는 가로 방향 도로 중 쓸 이유가 조금이라도 있는 도로들을 모아 놓으면, 그 도로들의 가중치는 아래쪽으로 갈수록 감소한다. 더 아래쪽에 있으면서 가중치도 더 크거나 같은 길은 전혀 쓸 이유가 없다.

비슷한 논리를 \(L\)보다 아래쪽에 있는 가로 방향 길들에 대해서 쓰면 어떻게 되는가? 비슷한 논리를 세로 방향 길들에 대해서 쓰면 어떻게 되는가?

힌트 9를 보려면 스크롤하자.

힌트 9

힌트 8에 대한 답: 쓸 이유가 있는 가로 방향 도로들을 모아 놓으면 아래쪽으로 갈수록 가중치가 감소하다가 최솟값을 찍은 뒤 다시 증가한다. 세로 방향 길도 마찬가지로 가중치가 오른쪽으로 갈수록 감소하다가 최솟값을 찍은 뒤 다시 증가한다. 다른 말로 이 두 수열 모두 ‘바이토닉’하다.

이 규칙에 따라 쓸 이유가 없는 길들을 걸러내는 것은 \(O(N+M)\)에 가능하다는 것을 아주 쉽게 알 수 있어야 한다 (그렇지 않다면 이 문제에 도전할 만한 실력이 아니다).

여기까지 왔다면 꽤 많이 온 것이다. 이쯤에서 힌트를 그만 보고 나머지는 스스로 하는 것을 도전해 보아도 괜찮을 수 있다 (단 아직 생각보단 먼 길이 남아있음을 알아 두자).

힌트 10을 보려면 스크롤하자.

힌트 10

오른쪽으로 \(x\)만큼 간 뒤 아래로 \(y\)만큼 가는 것은 아래로 \(y\)만큼 간 뒤 오른쪽으로 \(x\)만큼 가는 것과 도착지가 동일하다. 만약 두 번째 방법이 시간을 더 적게 쓴다면 바꾸는게 이득이다. 물론 반대로도 성립한다. 이를 이용하면 ‘이 길은 쓸 이유가 없군!’이라는 결론을 꽤나 유용하게 도출할 수 있다.

당연하고 매우 쉬운 말인 것 같지만, 이 사실을 이용한다는 것 자체가 풀이 방향성의 길을 꽤나 잡아줄 것이라 생각한다.

힌트 11을 보려면 스크롤하자.

힌트 11

힌트 9에서 사용할 이유가 없는 길들을 많이 걸러냈다. 하지만, 아직 더 걸러낼 수 있다. 어떻게 걸러낼지 더 고민해 보자.

바이토닉에 포함되어 있으면서, 바이토닉보다 조금 더 강한 조건이 무엇일까?

여기서 태그 중 하나가 도움이 될지도 모른다.

힌트 12를 보려면 스크롤하자.

힌트 12

사용하는 가로 방향 길 번호의 리스트 중 연속된 세 개 \(i < j < k\)를 고르자. 이때 \(i\)번째 가로 길에서 \(k\)번째 가로 길로 이동하는 과정은 다음과 같을 것이다.

가중치가 \(x\)인 세로 방향 길을 따라 \(j\)번째 가로 길로 이동한다.
\(j\)번째 가로 길을 따라 \(t\)칸 오른쪽으로 이동한다.
가중치가 \(y\)인 세로 방향 길을 따라 \(k\)번째 가로 길로 이동한다.

1번과 2번 단계를 힌트 10에 따라 대체를 시도해 보면, 원래 경로의 가중치는 \(x(j-i)+ A_j t\), 대체 경로의 가중치는 \(A_i t + y(j-i)\)이다. 즉 \(j\)번째 가로 길을 사용할 이유가 있기 위해서는 \(x(j-i) +A_j t < y(j-i) +A_i t\)여야 한다. 마찬가지로 2번과 3번 단계에도 비슷한 논증을 적용하면 \(y(k-j) + A_j t < x(k-j) + A_k t\)를 얻는다. 이제 이 식을 정리해서 무언가를 얻어 보자.

힌트 13을 보려면 스크롤하자.

힌트 13

\(x\)와 \(y\)를 소거하기 위해 첫 번째 부등식에 \(k-j\)를, 두 번째 부등식에 \(j-i\)를 곱한 뒤 변변 더하면 \(t\)가 약분되면서 \((k-j+j-i) A_j < (k-j) A_i + (j-i) A_k\)를 얻는다. 이를 \(A_j < \dfrac{(k-j)A_i + (j-i) A_k}{(k-j)+(j-i)}\)로 쓰면 어디서 많이 본 것 같은 내분점 공식이 나온다. 좌표평면 위에 점 \(\mathrm{I}(i,A_i), \mathrm{J}(j,A_j), \mathrm{K}(k,A_k)\)를 찍으면 \(\overline{\mathrm{IK}}\)의 \((j-i):(k-j)\) 내분점이 바로 \(\left(j,\dfrac{(k-j)A_i + (j-i) A_k}{(k-j)+(j-i)}\right)\)이다. 즉 \(\mathrm{J}\)는 \(\overline{\mathrm{IK}}\)보다 아래쪽에 있어야 한다.

또 다른 말로 하면? 사용할 이유가 있는 길들을 모아 놓고, 그 리스트에 속한 각각의 길에 대해 \(x\)좌표는 길 번호, \(y\)좌표는 길의 가중치인 점을 찍게 되면 이 점들은 아래로 볼록한 모양을 이룬다. 이는 당연히 세로 길들에 대해서도 성립한다.

그레이엄 스캔을 알고 있다면, 스택을 이용해 이 조건을 만족하는 길만을 걸러내는 방법을 알고 있을 것이다(그레이엄 스캔을 모르더라도 이 특수한 경우에는 \(x\)좌표가 증가만 하기 때문에 생각해내기 꽤 쉬운 편이다). 단 정렬이 필요하지 않기 때문에 선형 시간만으로 가능하다.

힌트 14를 보려면 스크롤하자.

힌트 14

정말 많은 길 걸러내기 작업이 있었다. 다행히도, 필요없는 길은 이제 충분히 걸러졌다.

이제 우리가 얻은 이 볼록성 조건을 이용해 어떻게 끝낼지 고민해 보자.

나머지 하나의 태그가 도움이 될지도 모른다.

힌트 15를 보려면 스크롤하자.

힌트 15

상황을 단순화해서, 세로 방향 길이 2개밖에 없다고 생각해 보자. 이 경우 우리는 어떤 가로 방향 길을 이용할지만 결정하면 된다.

볼록성을 이용해 필요 없는 가로 방향 길들은 모두 걸러냈다고 하자. 남은 길들 중 가장 위쪽의 가로 길을 이용할 때의 총 시간이 있을 것이다. 이제 이용하는 가로 길을 현재 가로 길에서 그 다음 가로 길로 바꿀 때 무엇이 바뀌는지 분석할 것이다.

두 개의 세로 길 중 왼쪽의 가중치를 \(x\), 오른쪽의 가중치를 \(y\)라 하자. 현재 선택된 가로 길이 \((i,A_i)\), 그 다음 가로 길이 \((j,A_j)\)라 하자. 이 좌표들의 의미는 힌트 13에서 만든 좌표와 같다. \(i\)번째 가로 길에서 \(j\)번째 가로 길로 선택을 변경할 때 변경되는 사항은 다음과 같다.

왼쪽 세로 길을 \(j-i\)만큼 더 사용한다.
오른쪽 세로 길을 \(j-i\)만큼 덜 사용한다.
\(i\)번째 가로 길을 사용하지 않는 대신 \(j\)번째 가로 길을 사용한다.

이 때문에 생기는 시간의 변화는 \((j-i)(x-y) + A_j - A_i\)이다. 이 값이 양수이면 \(i\)번째 가로 길의 선택을 유지하는 것이 이득이고, 음수이면 \(j\)번째 가로 길로 바꾸는 것이 이득이다. \((j-i)(x-y) + A_j - A_i > 0\)을 다르게 쓰면 \(\dfrac{A_j - A_i}{j-i} > y-x\)이다. 이때 좌변은 \((i,A_i)\)와 \((j,A_j)\)를 잇는 직선의 기울기이므로, 볼록성 조건에 따라 아래쪽으로 갈수록 증가만 한다. 즉 이 값이 음수에서 양수로 바뀌는 시점은 많아야 한 개이며, 최적의 길이 잘 결정된다.

따라서 이 단순한 조건 하에서 우리는 각 교차점에서 다음과 같은 결정만 하면 된다.

\((j-i)(y-x)\)와 \(A_j-A_i\)를 비교한다.
\((j-i)(y-x)<A_j - A_i\)이면 가로 길을 이용한다.
\((j-i)(y-x)>A_j - A_i\)이면 세로 길을 이용한다.

이 계산은 각 \(O(1)\)에 할 수 있으므로, 총 시간은 우리가 지나야 하는 총 교차점 수인 \(O(N+M)\)이 된다.

정말 거의 다 왔다. 이제 이 관찰을 임의 크기의 격자로 확장할 수 있겠는가?

힌트 16을 보려면 스크롤하자.

힌트 16

확장을 위해서는 다음 질문에 답해야 한다.

\((j-i)(y-x)\)와 \(A_j-A_i\)라는 값의 정체는 무엇인가?

이 값들이 애초에 어떻게 계산된 값들인지를 생각해 보면 답이 나온다.

\((j-i)(y-x)\)는 지금 가로 길을 선택함으로 인해 발생하는, 앞으로 세로 길에 추가로 쓸 시간이다. 즉 원래 \(x\)의 가중치로 갔어야 할 \(j-i\)의 거리를 가로 길을 선택함으로 인해 \(y\)의 가중치로 가게 되었다.
\(A_j-A_i\)는 지금 세로 길을 선택함으로 인해 발생하는, 앞으로 가로 길에 추가로 쓸 시간이다. 즉 원래 \(A_i\)의 가중치로 갔어야 할 \(1\)의 거리를 세로 길을 선택함으로 인해 \(A_j\)의 가중치로 가게 되었다.

즉 우리는 이 두 개의 ‘추가 시간 비용’을 비교해서, 더 낮은 비용을 매번 선택했던 것이다. 생각보다 매우 자연스러운 결론이다.

힌트 17을 보려면 스크롤하자.

힌트 17

이제 같은 논증이 임의 크기의 격자에도 비슷하게 적용된다고 믿고 확장을 시도해 보자. 현재 \(i\)번 가로 길과 \(p\)번 세로 길이 만나는 점에 있고 다음 ‘쓸 만한’ 가로 길이 \(j\)번, 다음 ‘쓸 만한’ 세로 길이 \(q\)번이라 하면,

가로 길을 선택함으로 인해 발생하는, 앞으로 세로 길에 추가로 쓸 시간은 \((j-i)(B_q-B_p)\)이다.
세로 길을 선택함으로 인해 발생하는, 앞으로 가로 길에 추가로 쓸 시간은 \((q-p)(A_j-A_i)\)이다.

따라서 우리의 전략은 다음과 같다.

\((j-i)(B_q-B_p) < (q-p)(A_j-A_i)\)이면 가로 길을 이용한다.
\((j-i)(B_q-B_p) > (q-p)(A_j-A_i)\)이면 세로 길을 이용한다.

볼록성을 이용해 쓸 이유가 없는 길을 걸러낸 뒤 이 전략을 사용하는 코드를 작성하면 AC를 받는다.

풀이의 증명

Proof by AC를 주장할 수도 있겠지만, 노트북을 덮기 전에 간단하게 증명(?) 정도는 하고 가자. 우선 볼록성을 이용해 팔요 없는 길을 모두 걸러낸 격자를 생각하자. 모든 경로는 다음과 같은 과정을 거쳐 만들 수 있다.

오른쪽으로 끝까지 간 뒤 아래로 끝까지 가는 경로로부터 시작한다.
현재 경로가 오른쪽으로 가다가 아래로 꺾는 지점이 존재한다고 하자. 이 ‘90도 회전’은 칸 하나를 ‘끼고’ 일어나는 회전이다. 이 칸을 오른쪽, 아래로 지나가는 대신 아래, 오른쪽으로 지나가는 것으로 변경한다.
2번 과정을 원하는 경로가 나올 때까지 반복한다.

2번 과정에서 얼마나 이득을 볼 수 있을까? 이 ‘칸’이 (위와 마찬가지로) \(i\)번과 \(j\)번 가로 길, \(p\)번과 \(q\)번 세로 길을 경계로 하는 칸이라고 하자. 이때 원래 경로는 \(A_i (q-p) + B_q (j-i)\), 대체 경로는 \(B_p (j-i) + A_j (q-p)\)의 시간이 걸리므로 더 걸리는 시간은 \((q-p)(A_j-A_i)-(j-i)(B_q-B_p)\)가 된다. 어딘가에서 많이 본 것 같은 식이다! 이 값이 음수라면 대체 경로(아래, 오른쪽)가 원래 경로(오른쪽, 아래)보다 이득이고, 양수라면 원래 경로가 더 이득이다. 다른 말로 하면 이 값이 음수라면 이 칸이 경로보다 위에 있는 것이 이득이고, 양수라면 아래에 있는 것이 이득이다.

그런데 \((q-p)(A_j-A_i)-(j-i)(B_q-B_p) = (j-i)(q-p)\left(\dfrac{A_j-A_i}{j-i}-\dfrac{B_q-B_p}{q-p}\right)\)이다. \((j-i)(q-p)\)는 양수이고, \(\dfrac{A_j-A_i}{j-i}\)와 \(\dfrac{B_q-B_p}{q-p}\)는 아주 많이 본 그 기울기들이다. 이 기울기들은 아래로, 오른쪽으로 갈수록 증가하므로 \(\dfrac{A_j-A_i}{j-i}-\dfrac{B_q-B_p}{q-p}\)는 아래로, 왼쪽으로 갈수록 증가한다. 따라서 이 값이 양수인 칸들과 음수인 칸들의 경계는 전반적으로 우하향 대각선을 그릴 수밖에 없다.

앗! 그런데 그 경계가 우리가 찾고 있는 최적의 경로이다! 왜냐하면 이 값이 음수인 칸들은 경로보다 위에, 양수인 칸들은 경로보다 아래에 있어야 하기 때문이다. 그런데 마침 경계가 올바른 경로이므로 (오른쪽 또는 아래로만 가니까), 그 경계가 최적해이다. 우리의 알고리즘은 지나가는 각 칸마다 그 값을 계산해서 경로가 그 칸을 위에 두어야 할지 아래에 두어야 할지 결정하고 있던 것이다. 증명 완료!