BOJ 4811 - 알약

문제

백준 온라인 저지 - 4811번

풀이 과정

알약을 하나 전체를 먹거나 반개를 먹어서 만들 수 있는 모든 문자열의 개수를 찾는 문제입니다.

완전탐색으로 접근하면 경우의 수가 너무 많기 때문에 중복된 연산을 많이 수행하게 됩니다.

대신 동적 계획법 을 활용해서 모든 경우의 수를 구하면 중복된 연산을 많이 줄일 수 있습니다.

dp[i][w][h] = 알약 한개가 W개, 반개가 h개 있을 때 i 날부터 시작해서 만들 수 있는 모든 문자열의 개수 라고 정의한다면

다음과 같은 점화식을 얻을 수 있습니다.

dp[i][w][h] = dp[i + 1][w][h + 1] + dp[i + 1][w + 1][h]

단 전자의 경우 `h < w` 여야 하며 후자의 경우는 `w < N(전체 알약 수)` 이어야 합니다.

코드

import sys

N = 0
memo = []


def eat_pill(day, w, h):
    if day == 2 * N - 1:
        return 1

    if memo[day][w][h] != -1:
        return memo[day][w][h]

    memo[day][w][h] = 0

    # 알약 반개 먹기
    if h < w:
        memo[day][w][h] += eat_pill(day + 1, w, h + 1)

    # 알약 한개 먹기
    if w < N:
        memo[day][w][h] += eat_pill(day + 1, w + 1, h)

    return memo[day][w][h]


def solution():
    global memo

    memo = [[[-1] * (N + 1) for _ in range(N + 1)] for _ in range(2 * N)]
    return eat_pill(0, 1, 0)


if __name__ == '__main__':
    while True:
        N = int(sys.stdin.readline())
        if N == 0:
            break

        answer = solution()
        print(answer)