'카탈란수' 태그의 글 목록

안녕하세요. 오랫만입니다. 이번 시간에는 제가 출제한 가희와 비행기 문제를 보도록 하겠습니다. 문제를 다 이해하셨다면, 구하려고 하는 것은 그리 어렵지 않음을 알 수 있습니다. 김포 공항에서 김해 공항까지 수평 거리가 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가 아닐 때, ..