4811. 알약 (Python)

4811번: 알약

 

풀이

 재귀를 통해서 경우의 수를 구할 수 있고, 2차원 dp는 다음과 같은 정보를 갖는다.

dp[w][h] : W가 w개 있고 H가 h개 있을 때 만들 수 있는 문자의 수 

 

 재귀 함수는 다음과 같이 정의되어 있다.

solve(w, h) -> w: 현재 갖고 있는 W의 개수, h: 현재 갖고 있는 H의 개수

 

 처음 재귀 함수의 호출은 solve(N-1, 1)과 같은 형태를 갖는다(N은 알약의 개수). 처음에는 온전한 형태의 약만 존재하기 때문에 문자열의 첫 번째 문자는 무조건 W가 오게 된다. 그렇기 때문에 W는 전체 알약의 개수 N에 -1을 해준만큼을 갖고 있게 되고 알약을 반으로 쪼갠 후 한 쪽은 다시 병에 넣기 때문에 H는 1개를 갖고 있게 된다.

 

 그 후에는 W를 쓰는 경우와 H를 쓰는 경우로 나누어 재귀적으로 호출한다. 이때, W를 전부 사용해서 H만 남아있을 경우에는(w == 0) H를 모두 사용해서 문자열을 완성하는 하나의 경우의 수밖에 없기 때문에 1을 return하고 h가 음수일 경우는 존재하지 않는 경우이므로 0을 return 하도록 설정하면 된다.

 

코드

def solve(w, h):
    if dp[w][h] != -1: # 이미 계산한 경우에는 그대로 리턴 
        return dp[w][h]
    dp[w][h] = 0

    if w == 0: # H만 남았을 경우에는 남은 H를 모두 사용하여 만드는 문자 하나의 경우만 존재
        dp[w][h] = 1
        return dp[w][h]
    if h < 0: # H가 음수 개 되는 경우는 없기 때문에 0을 리턴 
        return 0

    # W를 사용한 경우 + H를 사용한 경우 
    dp[w][h] = solve(w - 1, h + 1) + solve(w, h - 1)
    return dp[w][h]


if __name__ == '__main__':
    # dp[w][h] : W가 w개 있고 H가 h개 있을 때 만들 수 있는 문자열 경우의 수 
    dp = [[-1] * 31 for _ in range(31)] 

    while True:
        N = int(input())

        if N == 0:
            break
        
        # 문자열의 첫 번째 문자는 항상 W가 오기 때문에 N - 1개가 된다.
        # 알약 하나를 반으로 쪼갠 후 하나를 집어 넣기 때문에 초기 H의 개수는 1이 된다.
        print(solve(N - 1, 1))