문제
70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.
첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?
입력
입력은 최대 1000개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.
입력의 마지막 줄에는 0이 하나 주어진다.
출력
각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.
코드
while True:
n = int(input())
if n == 0:
break
dp = [[0]*(n+1) for _ in range(n+1)] # 행: W, 열: H
dp[0][0] = 1
for i in range(1, n+1):
dp[i][0] = dp[i-1][0]
for j in range(1, n+1):
if j > i:
continue
dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][n])
dp 배열의 행은 W의 개수, 열은 H의 개수이다. 알약이 온전한 한 조각이 쪼개져야만 반 조각이 되므로 이미 만들어진 문자열에는 H의 개수가 W의 개수보다 작거나 같아야만 한다. 그러므로 반복문을 돌 때 열의 인덱스(j)가 행의 인덱스(i)보다 큰 경우는 continue해주어야 한다. 그렇지 않다면 점화식은 다음과 같다.
$$dp[i][j] = dp[i-1][j]+dp[i][j-1]$$
W를 하나 추가하는 경우(dp[i-1][j])와 H를 하나 추가하는 경우(dp[i][j-1])를 더하면 된다.
'문제풀이 > DP' 카테고리의 다른 글
[Python/파이썬] 백준 2629번 양팔저울 (0) | 2023.10.10 |
---|---|
[Python/파이썬] 백준 20542번 받아쓰기 (0) | 2023.09.26 |
[Python/파이썬] 백준 13707번 합분해 2 (0) | 2023.09.08 |
[Python/파이썬] 백준 14226번 이모티콘 (0) | 2023.09.06 |
[Python/파이썬] 백준 17265번 나의 인생에는 수학과 함께 (0) | 2023.08.29 |