[BOJ] 백준 4811 알약 - Python/Java

문제 

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

4811번: 알약

해설

DP를 통해 문제를 해결할 때 고민하는 부분은 크게 세 가지입니다.

 

1. 현재 상황은 이전의 상황에서 어떻게 변하는가?

2. 상황의 변화를 표현하기 위해 필요한 변수는 몇 개인가?

3. DP 테이블의 초기화는 어떻게 해야하는가?

 

이 문제를 위 관점에서 정의해보겠습니다.

 

문제에서 주어진 각 시점에서 선택할 수 있는 변화는 '완전한 알약 하나를 먹거나', '반절짜리 알약 하나를 먹거나' 두 가지입니다.

 

따라서, 어떤 시점에서 필요한 변수는 완전한 알약의 개수와 반절짜리 알약의 개수인데요. 이 두 가지 변수를 DP의 변수로 정의하게 되면 어떤 시점에서 완전한 알약과 반절짜리 알약이 i, j개 일 때 그 이전에서의 상황 변화로 현재 상태를 표현할 수 있습니다. 좀 더 구체적으로 들여다보면 현재 i, j개의 알약이 있을 때는 완전한 알약 하나를 먹거나, 반절짜리 알약 하나를 먹게 되게 되면 그 이전의 상태로 현재 상태를 표현할 수 있다는 것이죠.

 

즉, dp[i][j] = 완전한 알약이 i개, 반절짜리 알약이 j(j > 0)개 있는 상황에서 나올 수 있는 경우의 수라면, dp[i][j] = dp[i-1][j+1] + dp[i][j-1]이 성립하고, 반절짜리 알약이 없는 상황(j = 0)이라면 단순히 dp[i][j] = dp[i-1][j+1]로 표현이 가능합니다.

 

그리고 i와 j에 대한 반복문을 증가하는 방향으로 설정하게 되면, dp[i][j]를 구할 때, dp[i-1][k]는 항상 미리 계산되어 있으므로 메모이제이션을 활용하는 데 문제가 없습니다.

 

마지막으로, 이 문제를 위와 같은 점화식으로 나타내기 위해서는 완전한 알약이 0개 있는 상황을 1로 초기화해야 합니다. 단순히 반절짜리 알약만 있다면 일렬로 쭉 나열하는 경우의 수라는 뜻이죠.

 

이를 코드로 구현하면 아래와 같습니다.

풀이 - 파이썬

# dp[i][j] = i개의 완전한 알약, j개의 반절짜리 약이 남았을 때 조합의 수
dp = [[0] * 31 for _ in range(31)]
for i in range(1, 31): # 반알짜리만 남아있으면 일렬로 나열
    dp[0][i] = 1

for i in range(1, 31):
    for j in range(30):
        if j == 0: # 완전한 알약 하나를 먹으면 반절짜리 알약이 하나 생긴다.
            dp[i][j] = dp[i-1][j+1]
        else: # 반절짜리 약을 하나 먹은 상황 + 완전한 알약 하나를 먹은 상황
            dp[i][j] = dp[i][j-1] + dp[i-1][j+1]
# 결과 출력           
while True:
    n = int(input())
    if n == 0: break
    print(dp[n][0]) # 결과 : n개의 완전한 알약이 있을 때 경우의 수

풀이 - 자바

package PS;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class B_4811 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // dp[i][j] = i개의 완전한 알약, j개의 반절짜리 약이 남았을 때 조합의 수
        double[][] dp = new double[31][31];
        for(int i = 1; i <= 30; i++){ // 반알짜리만 남아있으면 일렬로 나열
            dp[0][i] = 1;
        }

        for(int i = 1; i <= 30; i++){
            for(int j = 0; j < 30; j++){
                // 완전한 알약 하나를 먹으면 반절짜리 알약이 하나 생긴다.
                if(j == 0) dp[i][j] = dp[i-1][j+1];
                // 반절짜리 약을 하나 먹은 상황 + 완전한 알약 하나를 먹은 상황
                else dp[i][j] = dp[i][j-1] + dp[i-1][j+1];
            }
        }
        // 결과 출력 부분
        StringBuilder sb = new StringBuilder();
        while(true){
            int n = Integer.parseInt(br.readLine());
            if(n == 0) break;
            sb.append(String.format("%.0f", dp[n][0])).append('\n');
        }
        System.out.print(sb);
    }
}