문제

70세 박종수 할아버지는 매일 매일 약 반알을 먹는다. 손녀 선영이는 종수 할아버지에게 약이 N개 담긴 병을 선물로 주었다.

첫째 날에 종수는 병에서 약 하나를 꺼낸다. 그 다음, 그 약을 반으로 쪼개서 한 조각은 먹고, 다른 조각은 다시 병에 넣는다.

다음 날부터 종수는 병에서 약을 하나 꺼낸다. (약은 한 조각 전체 일 수도 있고, 쪼갠 반 조각 일 수도 있다) 반 조각이라면 그 약을 먹고, 아니라면 반을 쪼개서 한 조각을 먹고, 다른 조각은 다시 병에 넣는다.

종수는 손녀에게 한 조각을 꺼낸 날에는 W를, 반 조각을 꺼낸 날에는 H 보낸다. 손녀는 할아버지에게 받은 문자를 종이에 기록해 놓는다. 총 2N일이 지나면 길이가 2N인 문자열이 만들어지게 된다. 이때, 가능한 서로 다른 문자열의 개수는 총 몇 개일까?

입력

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

입력의 마지막 줄에는 0이 하나 주어진다.

출력

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

solved.ac 기준 골드5 문제. 어렵다.

한참을 궁리했지만 어떻게 풀어야 할지 감이 안 잡혔다. 깔끔하게 푼 이의 답안을 찾았다. (참고 : https://dirmathfl.tistory.com/241)

from sys import stdin
def dfs(w, h):
    if dp[w][h]:
        return dp[w][h]
    if w == 0:
        return 1
    dp[w][h] = dfs(w-1, h+1)
    if h > 0:
        dp[w][h] += dfs(w, h-1)
    return dp[w][h]

dp = [[0] * 31 for _ in range(31)]
while True:
    n = int(stdin.readline())
    if n == 0:
        break
    print(dfs(n, 0))

코드를 봐도 잘 이해가 안 된다. dp[w]를 W가 입력되는 리스트로, dp[w][h]를 H가 입력되는 리스트로 계산해서 w값을 1씩 빼고 h값을 1씩 더하면서 재귀로 푸는 방식 같은데, 반 개(h)가 남아 있으면 그 숫자만큼 경우의 수에 더해주는 식도 있다. 잘 모르겠다.

더 쉽게 푼 사례 발견.

while True:
    n = int(input())
    if n == 0:
        break
    r = 1
    for n in range(2*n, n, -1):
        r *= n # 뒤쪽 절반은 r에 곱해줌. n도 n+1 이 됨.
    for i in range(1, n+1):
        r //= i
    print(r)

for n in range(2*n, n, -1)이 뒤쪽 절반을 거꾸로 탐색하며 r에 곱해주는 건 알겠는데, 왜 for n으로 해서 n값을 n+1로 바꿔주는지는 잘 모르겠다.

이 문제 풀이를 공부하면서 ‘카탈란 수‘란 걸 처음 들었다.

카탈린 수를 구하는 가장 유명한 문제는 ‘괄호 문자열‘이다. 올바른 괄호 문자열은 ‘(‘와 ‘)’가 동일한 숫자로 이뤄져야 한다. ‘(()())’은 올바른 괄호 문자열이지만, ‘())’은 올바른 괄호 문자열이 아니다. 알약 문제 역시 같은 유형이다. W와 H가 동일한 수로 구성돼야 한다.

카탈린 수를 구하는 공식은… 음, 외우면 된다.

구하려는 쌍이 n개이고, 총 경우의 수를 x라고 하면

${x}={\frac{(2n)!}{n!(n+1)!}}$

이다. 공식만 보면 무척 간단하다.

‘올바른 괄호’, ‘산 만들기’, ‘대각선 피해가기’, ‘다각형을 삼각형으로 나누기’ 등이 카탈린 수열을 응용한 문제 유형들로 꼽힌다고.

카탈린 수를 구하는 공식으로 이 문제를 풀면, 더 간단해진다.

from math import factorial as fc 
def catalan(n):
    return fc(2*n) // (fc(n) * fc(n+1))
while True:
    n = int(input())
    if n == 0:
        break
    print(catalan(n))

카탈린 수를 수학으로 설명해놓은 글도 있는데, 요것까진 못 보겠다.

마지막으로, 이 방법이 있네.

코드를 보면, [1, 1]로 구성된 리스트(l)를 초기값으로 놓고 리스트의 맨 앞과 맨 뒤에서 숫자를 하나씩 곱해가며 그 합을 구하는 식이다. 이 합이 n개 약에 대한 경우의 수다. 직접 코드를 보면 이해가 더 쉽다.

l=[1,1]
for i in range(31):
	c = 0
	for j in range(len(l)):
		c += (l[j] * l[-1-j])
	l.append(c)
n = int(input())
while n:
	print(l[n])
	n = int(input())

n=2라면 l[2]는 (1*1)+(1*1)=2가 된다. 같은 방법으로 l[3]은 (1*2)+(1*1)+(1*2)=5이고, l[4]=(1*5)+(1*2)+(2*1)+(5*1)=14이다.

while문을 0이 입력될 때 종료되도록 할 때, 저렇게 짜는 방법도 있네.

배울 게 한참 남았다.

[문제 보기]