[DP] 백준 4811번 - 알약

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

4811번: 알약

백준 4811번 알약 문제다. 

DP 유형의 문제로 생각할 수 있다.

 

DP[W][H]라고 하는 배열이 온전한 알약이 W개, 반쪽짜리 알약이 H개 있을 때 만들 수 있는 문자열의 개수로 설정해보자.

 

문제의 조건을 보면 N개 담긴 병을 선물했고, 그 중 한 개를 쪼개 먹은 뒤 온전한 알약이 N-1개, 반 개 짜리 알약이 한 개 있는 상황에서 시작하는 것이므로 최종적으로 DP[N-1][1]의 값을 찾으면 된다.

(예제 1 입력값의 결과가 1인 것에 주목하자. 이 경우 온전한 알약은 0개, 쪼개진 알약의 개수는 1개에서 시작하게 된다.)

 

먼저 DP의 기초인 기저값을 먼저 설정해주는 것이 필요했다.

온전한 알약은 0개이며 쪼개진 알약이 0개 이상 존재할 때 만들 수 있는 문자열의 개수는 1개이므로

DP[0][0] ~ DP[0][30] 을 1로 초기화해준다.

 

그 다음, W=1 부터 W=30까지 아래의 경우에 대해 DP 배열값을 설정해준다.

1) 쪼개진 알약이 없는 경우(H == 0) 

DP[W][H] = DP[W-1][1];

 

2) 온전/쪼개진 알약모두가 있는 경우

DP[W][H] = DP[W-1][H+1] + DP[W][H-1];

 

1번의 경우는 온전한 알약을 먹을 수 밖에 없는 경우이므로 한 개를 줄이고 쪼개진 알약 1개를 추가해준 것이다.

2번의 경우는 온전한 알약을 먹었을 경우 1을 빼주고 쪼개진 알약 하나를 추가해준 것과

                 온전한 알약을 먹지 않고 쪼개진 알약 하나를 먹는 경우를 추가해준 것을 더하는 경우다.

 

위 두 점화식을 바탕으로 구현하면 다음과 같다.

 

#include <stdio.h>
#pragma warning(disable:4996)
 
long long dp[31][31];
 
int main(){
    int N;
    for (int i = 0; i < 31; i++){
        dp[0][i] = 1;
    }
    for (int w = 1; w < 31; w++){
        for (int h = 0; h < 31; h++){
            if (h == 0){
                dp[w][h] = dp[w - 1][1];
            }
            else{
                dp[w][h] = dp[w - 1][h + 1] + dp[w][h - 1];
            }
        }
    }
    scanf("%d", &N);
    while (N != 0){
        printf("%lld\n", dp[N - 1][1]);
        scanf("%d", &N);
    }
    return 0;
}