안녕하세요. 오랫만입니다. 이번 시간에는 제가 출제한 가희와 비행기 문제를 보도록 하겠습니다.

 


 문제를 다 이해하셨다면, 구하려고 하는 것은 그리 어렵지 않음을 알 수 있습니다. 김포 공항에서 김해 공항까지 수평 거리가 d일 때, 조건에 맞게 비행할 수 있는 가짓수를 구하는 것인데요.

 

 

 x인 지점에서 비행기의 고도가 h라고 해 보겠습니다. 그러면 x-1인 지점에서부터 고도가 1만큼 하강하거나, 혹은 고도가 1만큼 상승하는 이 두 가지 경우밖에 없습니다. 그래서, dp[x][h]를 x인 지점에서 고도가 h인 경우라고 정의하면, dp[x][h]는 dp[x][h-1] + dp[x][h+1]이 됩니다.

 

 그런데, 예외가 있습니다.

 

 

 중간에 착륙하는 경우는 없다고 했어요. 그렇기 때문에, x가 0이거나 d가 아닐 때, dp[x][0]의 값은 0이 되어야 합니다. 그러므로, x가 1일 때 부터 d-1일 때 까지 고도가 0인 지점에 대해 경우의 수를 구할 필요가 없습니다.

 

 

 우리가 구해야 하는 것은 dp[d][0]입니다. d만큼 갔을 때 고도가 0인 가짓수를 구하면 되는데요. 이것은 그냥 dp[d-1][1]과 같습니다. 따라서 아래와 같은 코드로 정답을 맞출 수 있습니다.

 

 

 코딩 테스트 대비 문제였기 때문에 d를 늘리거나 추가적인 제약 조건이 있지는 않았습니다.

 


 그런데 카탈란 수로도 풀 수 있습니다. 카탈란 수는 올바른 괄호쌍의 가짓수를 구하는 것과 관련이 있는데요. 비행기가 고도를 올리는 것을 (, 내리는 것을 )로 매칭해 봅시다. 고도가 0이 되는 경우에는 중간에 괄호쌍이 맞지 않는 경우가 생길 수가 있어요. 그래서 이러한 경우는 배제하고 생각해야 해요.

 

 어떻게 잘 해서 다시 d-1인 지점에서 고도가 1이 되었다고 해 봅시다. 가능한 경우 중 하나를 그림으로 그려 봅시다.

 

 

 

 이것은 ()(())과 매칭이 됩니다. 만약에 중간에 고도 0이 되었다면 중간에 이미 올바른 괄호쌍이 아니게 될 겁니다. 카탈란 수와 관련이 있다는 사실을 간파했다면, d가 100만 정도 되는 경우에도 모듈러가 소수이기 때문에 문제 없이 계산할 수 있습니다. 이러한 것을 모른다고 해도, 가짓수를 나눠 보면 간파를 하실 수 있습니다.

 

 

 먼저 x = 1인 지점부터 x = d-1인 지점까지 생각해 봅시다. 일단 1에서 2로 갈 때 고도를 올립니다. 그리고 d-2에서 d-1로 갈 때 고도를 내려요. 2에서부터 d-2일 때 까지 고도를 2 이하로 낮추지 않는 경우수는 어떻게 구하면 될까요?

 

 

 2에서부터 d-1일 때 까지 고도가 떨어지지 않으면서 2일 때의 고도와 d-2일 때 고도가 같으려면 d-4만큼 갈 동안 2일 때 이상의 고도만 유지하면 됩니다. dp[x]를 지점 1부터 x까지 비행기가 오르락 내리락 했을 때, 지점 1에서의 고도를 그대로 유지하는 경우 수라고 해 봅시다.

 

 저 경우는 dp[d-2]를 구해야 하는 것이고 dp[d-4]를 이미 알고 있네요. 따라서, 일단 dp[d-2]의 값은 dp[d-4]가 됩니다. 그런데, 이런 경우만 있을까요?

 

 

 그렇지 않아요. 이런 식으로 중간에 고도가 처음 시작했던 곳과 같아져 버리는 경우도 있어요. 이러한 경우를 모두 합산해 줘야 해요. 그런데 여기서 함정이 하나 있어요. 만약에 이렇게 묶어버렸다면, 이런 상황에서는 어떨까요?

 

 

 같은 경우인데 여러 번 세지겠죠? 왼쪽 네모는 아무렇게나 가도 상관이 없는데 오른쪽 네모는 고도가 2 이하로 떨어지면 안 된다는 조건을 걸면 이러한 중복되는 경우를 걸러버릴 수 있어요.

 

 

 즉, dp[d-2]를 구할 때, 왼쪽 네모의 가로 길이가 k였다면 오른쪽 네모의 가로 길이는 (d-2)-k-2가 됩니다.

 

 

 14번째 줄에 dp[j]*dp[i-j-2] 부분이 있는데요. dp[i-j]가 아니라 dp[i-j-2]를 곱하는 이유이기도 합니다. 정확하게 카탈란 수랑 동치이고, 소수로 나눈 나머지를 구한다면, 이를 매우 빠르게 구할 수 있는 방법이 있습니다. 저는 카탈란 수를 O(d^2)의 솔루션으로 구했습니다.