백준 4811 c++ "알약" -PlusUltraCode-

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

 

[필자 사고]

DP 탑다운 및 바텀업 둘다 가능한 문제다.

필자는 바텀업 방식으로 풀었고 해당 문제만의 특이한 매력은

W가 반드시 먼저 와야 된다는 제약조건이다.

즉 바텀업 방식으로 구현할때 H가 W보다 크면 절대로 안된다.

반드시 H는 W보다 작아야 된다.

사소한거지만 이러한 조건하나가 문제를 풀수 있을지 못할지를 결정하는걸 배웠따.

 

아래는 상세한 코드 해설이다.

[코드 해설]

2. DP 테이블 정의

이 문제에서 DP 테이블 dp[w][h]는 다음을 의미합니다:

• w: 아직 쪼개지 않은 (Whole) 알약 개수
• h: 이미 반으로 쪼개져 있는 (Half) 알약 개수
• dp[w][h]: W(Whole)를 w개, H(Half)를 h개 사용했을 때 만들 수 있는 문자열의 개수

따라서, 최종적으로 dp[n][n]의 값을 출력하면 문제의 정답을 얻을 수 있습니다.

---

3. 점화식 유도

각 단계에서 두 가지 선택이 있습니다:

1. W(Whole) 사용: 약을 하나 꺼내어 반을 먹고 반을 병에 넣습니다.
   → dp[w][h] += dp[w - 1][h + 1]
   (즉, w-1개의 Whole을 남기고, h+1개의 Half가 추가됨)
2. H(Half) 사용: 반쪽을 먹습니다.
   → dp[w][h] += dp[w][h - 1]
   (즉, h-1개의 Half를 남김)

---

4. DP 배열 초기화

초기 상태에서는 w = 0일 때, 남은 Half만 사용할 수 있으므로 경우의 수는 1입니다.
즉, dp[w][0] = 1을 설정합니다.

[소스 코드]

#include <iostream>
using namespace std;
typedef long long ll;

ll dp[33][33];

int main() {
    
    for (int h = 0; h <= 30; h++) {
        for (int w = 0; w <= 30; w++) {
            if (h > w) continue;
            if (h == 0) dp[w][h] = 1;
            else dp[w][h] = dp[w - 1][h] + dp[w][h - 1];
        }
    }

    int n;
    while (1) {
        cin >> n;
        if (n == 0)break;
        cout << dp[n][n] << "\n";
    }
}