4811번: 알약

문제

할아버지는 매일 약 반 알을 먹습니다. 약병에 들어있는 온전한 알약 N개가 주어질 때, 할아버지는 다음 규칙에 따라 약을 먹습니다.

1. 약병에서 무작위로 약을 하나 꺼냅니다.
2. 온전한 알약이라면 반으로 쪼개서 한 조각을 먹고, 남은 반 조각을 다시 약병에 넣습니다. (이때 'W'를 기록)
3. 반쪽짜리 알약이라면 그대로 먹습니다. (이때 'H'를 기록)

총 2N일을 거쳐 약을 모두 먹었을 때, 기록된 길이가 2N인 문자열이 나올 수 있는 서로 다른 경우의 수를 구하는 문제입니다.

• 입력: 각 줄에 테스트 케이스 N (1 ≤ N ≤ 30)이 주어집니다. 입력의 마지막 줄에는 0이 주어집니다.
• 출력: 각 테스트 케이스에 대해 가능한 서로 다른 문자열의 개수를 출력합니다.

링크: https://www.acmicpc.net/problem/4811

풀이: 2차원 배열과 반복문을 활용한 바텀업(Bottom-Up) DP

2중 반복문을 사용하여 작은 문제부터 차근차근 정답을 누적해 나가는 방식입니다. N의 상한선이 30으로 작기 때문에, 입력을 받기 전에 미리 최대 크기(30)까지의 모든 경우의 수를 계산해 두면(Precomputation) 테스트 케이스가 여러 번 주어져도 O(1)의 속도로 빠르게 응답할 수 있습니다.

• 상태 정의: dp[w][h]를 온전한 알약이 w개, 반쪽 알약이 h개 남았을 때 문자열을 완성할 수 있는 경우의 수로 정의합니다.
• 기저 조건 (Base Case): 온전한 알약이 하나도 남지 않은 상태(w = 0)라면, 병에는 반쪽짜리 알약만 남아있게 됩니다. 이 경우 선택지는 반쪽짜리 알약을 계속 꺼내는 것 1가지뿐이므로, 모든 h에 대해 dp[0][h] = 1로 초기화합니다.
• 점화식 적용 (반복문 순회): 온전한 알약 w를 1개부터 30개까지, 반쪽 알약 h를 0개부터 30개까지 순회하며 DP 배열을 채웁니다.
  1. 반쪽 알약을 꺼내는 경우: 현재 병에 반쪽 알약이 1개 이상 존재해야(h > 0) 가능합니다. 이 경우 반쪽 알약의 개수만 1개 줄어들게 되므로 dp[w][h] += dp[w][h - 1]을 더해줍니다.
  2. 온전한 알약을 꺼내는 경우: 온전한 알약을 하나 꺼내어 반으로 쪼개어 먹고 남은 반쪽을 넣으므로, 온전한 알약은 1개 줄고 반쪽 알약은 1개 늘어납니다. 따라서 dp[w][h] += dp[w - 1][h + 1]을 더해줍니다.
• 정답 도출: 입력을 받을 때마다, 초기에 주어진 상태인 "온전한 알약 N개, 반쪽 알약 0개"에 해당하는 dp[N][0] 값을 출력합니다. N이 30일 경우 결괏값이 int형의 범위를 초과하므로 반드시 long 타입의 2차원 배열을 사용해야 합니다.

코드

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // dp[w][h] : 온전한 알약 w개, 반쪽 알약 h개가 남았을 때 남은 기간의 가능한 문자열 수
        long[][] dp = new long[31][31];

        // 1. 기저 조건: 온전한 알약이 0개라면 반쪽 알약만 꺼내야 하므로 경우의 수는 1
        for (int h = 0; h <= 30; h++) {
            dp[0][h] = 1;
        }

        // 2. 바텀업(Bottom-Up) 방식으로 DP 배열 채우기
        for (int w = 1; w <= 30; w++) {
            for (int h = 0; h <= 30; h++) {
                
                // 반쪽짜리 알약을 꺼내는 경우 (반쪽 알약이 1개 이상 있을 때만 가능)
                if (h > 0) {
                    dp[w][h] += dp[w][h - 1];
                }
                
                // 온전한 알약을 꺼내는 경우 (온전한 알약 1개 감소, 반쪽 알약 1개 증가)
                // (배열의 인덱스를 초과하지 않도록 보완)
                if (h < 30) {
                    dp[w][h] += dp[w - 1][h + 1];
                }
            }
        }

        // 3. 입력에 따라 미리 계산된 결과 출력
        while (true) {
            int n = Integer.parseInt(br.readLine());
            if (n == 0) break;

            // 처음에 온전한 알약 n개, 반쪽 알약 0개로 시작
            bw.write(dp[n][0] + "\n");
        }

        bw.flush();
    }
}

알고리즘 분류

수학 (Mathematics), 다이나믹 프로그래밍 (Dynamic Programming)