Coding 공부

def dfs(W,H):
    if W == 0:
        return 1
    if dp[W][H]:
        return dp[W][H]
    dp[W][H] = dfs(W-1,H+1)
    if H>0:
        dp[W][H] += dfs(W,H-1)
    return dp[W][H]



while True:
    N = int(input())

    if not N:
        break
    dp = [[0]*31 for _ in range(N+1)]

    print(dfs(N,0))

재귀적으로 푸는 방식이다.

한알로 먹는 먹을수 있는 개수를 W, 반알로 먹을 수 있는 개수를 H로 두고 재귀적으로 풀면 된다.

원래 들어온 W,H에서 기본적으로 W가 남아있으면, 한알을 꺼내먹을수 있기에 W-1,H+1로 함수를 실행시켜준다.

그리고 만약 H가 있다면, 반알을 먹을수도 있으므로, W,H-1로 함수를 실행시켜준다.

그러다가 한알짜리 알약이 전부 떨어지면, 남은경우는 반알을 전부 먹는것이므로 return 1을 해주며, 중단해준다.

이렇게 해서 전체 날짜에서 먹을수 있는 날짜를 구하면 된다.

dp = 31*[0]
dp[1] = 1
dp[0] = 1


for n in range(2,31):
    for i in range(n):
        dp[n] += dp[i]*dp[n-i-1]

while True:
    N = int(input())
    if not N:
        break
    print(dp[N])

 위와 같은 형태의 문제를 카탈란 수라고 한다. 자세한 설명은 아래의 사이트에서 읽어보면 된다.

   카탈란 수 설명 출처 : suhak.tistory.com/77

카탈란 수의 점화식을 이용해서 쉽게 푸는 방법도 있다.