https://www.acmicpc.net/problem/8895
| 시간 제한 | 메모리 제한 |
| 1초 | 256MB |
문제
높이가 1, 2, ..., n인 막대 n개가 일렬로 배치되어 있다. 막대를 왼쪽이나 오른쪽에서 보면, 큰 막대가 뒤에있는 작은 막대를 가리게 된다. 아래와 같이 4개의 막대로 이루어진 두 배치를 살펴보자.
위의 두 배치는 모두 왼쪽에서 봤을 때 막대가 한 개 보이고, 오른쪽에서 봤을 때는 막대가 두 개 보인다.
막대의 개수 n과 왼쪽에서 봤을 때 보이는 막대의 개수 l, 오른쪽에서 봤을 때 보이는 막대의 개수 r이 주어진다. 이때, 이러한 결과를 만드는 배치의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, n, l, r이 주어진다. (1 ≤ l, r ≤ n ≤ 20)
출력
각 테스트 케이스마다, 입력으로 주어진 값에 해당하는 배치의 수를 출력한다.
풀이
n의 범위가 20으로 매우 작다. 혹시 직접 구하는 문제인가?
20개의 막대를 나열하는 방법은 243경이 넘는다고 한다.
이런 답없는 수준의 조합론스러운 문제는 이제 dp로 풀릴 것 같다는 감이 온다. 일단 아직 정리된 식이 하나도 없지만 dp배열을 만들어 놓고 점화식을 생각해보기로 한다.
dp[n][l][r] = n개의 막대를 왼쪽에서 l, 오른쪽에서 r개의 막대가 보이도록 나열하는 방법의 수
이렇게 정의를 해놓고 생각해보자. dp[n][l][r]을 구성하는데 하위 원소들인 dp[n - 1][p][q] 이런 애들이 쓰일 수 있을까? 여기서 이 아이디어를 떠올렸다.
5개로 만들어진 왼쪽 같은 배치가 있다고 했을 때, 여기에 가장 긴 막대를 하나 추가하는 것으로 다음 값을 구성해나갈 수 있을 것 같았다. 여기에 문제가 한 가지 있다. 위의 예시에서 dp[5][2][3]의 값을 단순히 다음 값들에 더해주기만 하면 된다는 아이디어였는데, 이게 이렇게 계산되지 않는다.
왼쪽과 같은 배치는 보이는 막대만 표시하면 오른쪽과 같다. 그런데 왼쪽 막대를 놓고 가장 긴 막대를 끼워넣는 경우를 생각해봤을 때, 다음 경우가 한 가지 경우로 처리되면 안된다.
세 가지 모두 dp[6][3][2]로 이어지는 경우지만 각각 다른 방법으로 처리되므로 dp[5][2][2]에서 따로 처리되어야 한다. 이런 경우를 처리하다 보면 결국 거의 모든 배치를 다 따져봐야 하기도 하고, 무엇보다 이런 경우를 하나하나 찾도록 하는 게 쉽지가 않아보인다. 하지만 추가하는 막대가 가장 긴 막대가 아니라면?
가장 짧은 막대를 추가하는 것으로 식을 다시 생각해보자. dp[n][l][r]은 다음 세 가지 경우로 구성될 수 있게 된다.
각각의 경우로 dp[n][l][r]이 구성되는 점화식은 다음과 같다.
왼쪽 끝: dp[n][l][r] += dp[n - 1][l - 1][r]
가운데 아무데나: dp[n][l][r] += dp[n - 1][l][r] (보이는 막대 수에 영향이 없음)
오른쪽 끝: dp[n][l][r] += dp[n - 1][l][r - 1]
그리고 가운데 어디든 끼워도 같은 결과가 나오므로 가운에 끼워넣을 수 있는 n - 2개의 칸이 모두 같은 경우의 수를 이어 받는다. 따라서 점화식은 이렇게 정리된다.
dp[n][l][r]
= dp[n - 1][l - 1][r] + dp[n - 1][l][r - 1] + (dp[n - 1][l][r] * (n - 2))
이제 n = 20까지의 모든 값을 미리 구성해 놓고 n, l, r에 대한 값을 출력하면 된다. 전체 dp 배열 구성에 소모되는 시간은 O(n^3)이지만 n이 20밖에 되지 않으니 사실상 O(1)이다.
정답 코드
import sys
input = sys.stdin.readline
def solution():
dp = [[[0] * 21 for _ in range(21)] for _ in range(21)]
dp[1][1][1] = 1
for n in range(1, 21):
for l in range(1, n + 1):
for r in range(1, n - l + 2):
dp[n][l][r] += dp[n - 1][l][r - 1]
dp[n][l][r] += dp[n - 1][l - 1][r]
dp[n][l][r] += dp[n - 1][l][r] * (n - 2)
for _ in range(int(input())):
n, l, r = map(int, input().split())
print(dp[n][l][r])
solution()
