백준 4811번 - 알약

www.acmicpc.net/problem/4811

4811번: 알약

오랜만에 정말 오랫동안 고민한 문제다.

 

물론 새벽이라 피곤했다는 핑계가 있지만.. 

최근 들어서는 오래 고민하는 습관을 버리려고 노력했는데 실패..

 

도저히 떠오르지가 않아서 구글링을 해보았다.

 

더 놀라운건 구글링을 한 페이지 가까이했는데도 이해가 잘 안 간다........ㅠ

 

너무나도 길고 복잡한 재귀 코드들... 난 이해하고 싶지 않았다

(제가 구글링을 하면서 느낀 건데 코드가 간단할수록 이해하기 좋더라고요..

그래서 스포? 지만 저는 엄청 간단하게 짰어요)

 

솔직히 포스팅을 해야 할지 말지 고민을 했는데 그래도 남겨놔야 다시 공부할 수 있으니까 지금까지 이해한 것을 바탕으로 작성해보려 한다.

 

 

1. DP 배열 정의

 

DP[W][H] = 큰 알약 W개와 작은 알약 H개를 먹을 수 있는 경우의 수

 

대부분의 블로그들이 이렇게 말을 하고 있는데 저 말을 쉽게 풀어쓰자면

 

W와 H로 만들 수 있는 문자열들 중 문제의 조건에 부합하는 경우의 수!

 

(여기서 말하는 조건이란 당연히 W를 뽑아야 H가 생긴다 이거겠죠? 하도 봤더니 문제 다 외웠어)

 

 

2. Bottom-up 방식의 풀이

 

이 부분 역시 좌절을 겪은 부분이다..

 

딴 블로그 글들을 보면 아마 대부분 재귀 형태의 top-down방식으로 풀었을 것이다.

도대체 왜!!! 쉬운 bottom-up 풀이를 놔두고 top-down으로 풀어재끼냐고!!!

 

어쨌든 bottom-up으로 풀기 위해 점화식을 생각해보면

 

먼저 w = 1 , h = 0부터 시작해야 함은 당연하다. (반드시 처음에는 큰 알약 1개를 뽑을 수 있으니까)

 

dp[1][0] = 1       ->  'W'

dp[2][0] = 1       ->  'WW'

...

dp[n][0] = 1       ->  'WWW ...  WW'

 

dp배열을 정의한 대로 생각해보면 W를 w개 써서 문자열을 만드는 방법은 각 1개씩만 존재한다.

 

다음으로 h = 1 일 때를 생각해보자.

 

dp[1][1] = 1       ->  'WH'

dp[2][1] = 2       ->  'WWH', 'WHW'

dp[3][1] = 3       ->  'WWWH', 'WWHW, 'WHWW'

...

 

자 이제 분석해보자.

 

dp[3][1], 즉 'W' 3개와 'H' 1개로 나타낼 수 있는 문자열은

그저 'W'와 'H'로 표현할 수 있는 길이가 4인 문자열들 중 조건을 만족하는 경우의 수 일 뿐이다.

 

자. 여기까지 이해했다면 다음이 중요하다.

 

위의 문장을 해석해보면

 

'W'와 'H'로 표현할 수 있는 길이가 4인 문자열 = 

'W'와 'H'로 표현할 수 있는 길이가 3인 문자열 + 'W' or 'H' 이다!

 

그럼 해당 경우(길이가 3인 문자열)들을 모두 나열해 보면

 

dp[3][0]

dp[2][1]

dp[1][2]

dp[0][3]

 

이 4가지가 될 것이다.

 

이때, 문제의 조건에 의해 반드시, 어떤 경우에서든 w => h 여야 한다.

 

따라서 조건을 만족시키는 dp 배열의 합으로 표현해보면

dp[3][1] = (dp[3][0] + 'H')  +  (dp[2][1] + 'W') 라는 것이다!!!!   (요 부분이 핵심!!)

 

자 이제 우리는 점화식을 구할 수 있다.

 

점화식 : dp[w][h] = dp[w - 1][h] + dp[w][h - 1]

 

항상 dp를 풀 때 자주 말하는 말이 

dp문제에서 점화식을 구했다? 그때부턴 그냥 구현 문제에 불과하다.

 

코드는 다음과 같다.

 

#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";
    }
}

음.. 뭔가 정리하면서 다시 이해가 된 느낌이닼ㅋㅋ

 

오래 고민한 만큼 너무 허무하지만 다시 한번 dp의 벽을 느끼고 간다..