[백준 4811번] 파이썬 - 알약

백준 4811 - 알약

시간 제한 1초, 메모리 제한 256MB

# 조건

• 70세 박종수 할아버지는 매일 매일 약 반알을 먹는다.
• 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.
• 첫째 날에 종수는 병에서 약 하나를 꺼낸다.
• 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.
• 다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다)
• 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.
• 종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다.
• 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다.
• 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다.
• 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

• 입력은 최대 1000개의 테스트 케이스로 이루어져 있다.
• 각 테스트 케이스는 한 줄이며, 병에 들어있는 약의 개수 N ≤ 30 가 주어진다.
• 입력의 마지막 줄에는 0이 하나 주어진다.

출력

• 각 테스트 케이스에 대해서 가능한 문자열의 개수를 출력한다.

# 접근 방법

• N개의 알약으로 2N 길이의 문자열을 만드는 경우의 수를 구하는 문제이다.
• 따라서, 과거의 결과를 저장해서 사용하기에 좋은 DP를 활용해주었다.
• 이 문제의 핵심은, 2N 길이의 문자열을 만드는데 H가 등장하는 위치 앞 쪽에는 H보다 W가 많거나 같아야 되는 것이다.
• w와 h로 만드는 문자열을 표로 만들어 보면 이해가 잘 된다.
• 행을 w의 개수 0 1 2 3 4 5, 열을 h의 개수 0 1 2 3 4 5로 정한 뒤 빈 칸을 채워나간다.
  • i는 h의 개수, j는 w의 개수를 인덱스로 표현하는 것이다.
  • w가 1개 나왔다면 h가 1개 나올 수 있으므로 1을 넣어준다.
  • w가 2개 사용된 문자열은 ww 밖에 없으므로 1
  • w가 2개 사용되고 h가 1개 사용된 문자열은 WWH, WHW 이므로 2
  • W가 2개, H 2개 사용 또한 wwhh, whwh이므로 2개이다.
• 여기서 규칙을 보면 바로 위와, 왼쪽을 더한 값이 현재 만들려는 문자열의 개수와 같다는 것을 알 수 있다.
• 즉, dp[i][j] = dp[i-1][j] + dp[i][j] 가 되는 것이다.

h|w 0 1 2 3
0   0 1 1 1
1   x 1 2 3
2     x 2 5
3

import sys
input = sys.stdin.readline

dp = [[0] * 31 for _ in range(31)]
dp[0] = [1] * 31
dp[0][0] = 0
for i in range(1, 31):
    for j in range(1, 31):
        if i > j:
            continue
        dp[i][j] = dp[i-1][j] + dp[i][j-1]

while True:
    n = int(input())
    if n == 0:
        break
    print(dp[n][n])

# 카탈란 수

• 올바른 괄호의 수, n+2각형을 n개의 삼각형으로 자르기와 같은 문제를 해결할 때 사용하는 조합론에서 자주 등장하는 수이다.
• 아래의 점화식을 만족한다.

• 이 점화식을 풀이하면 (2n)! / (n+1)!(n)! 이 되고 정리하면 2N! / (N+1)(N!)^2가 된다.

import sys  
input = sys.stdin.readline  
from math import factorial  

while True:  
    n = int(input())  
    if n == 0:  
        break  
    result = factorial(2*n) // ((n+1) * factorial(n)**2)  
    print(result)