백준 4811 알약 (C++)

4811번: 알약

dp를 이용한 문제이다. w와 h 개수에 따른 경우의 수를 dp를 이용해 구해주었다. 먼저 w=0인 경우는 h만 남았다는 의미이므로 나머지 h를 뒤에 이어 붙이는 경우 밖에 없기에 경우의 수는 1이 된다. 그리고 h=0인 경우는 w만 남았다는 의미이므로 dp[w][h] = dp[w-1][h + 1]이 된다. 그 외에는 w나 h가 올 수 있기때문에 dp[w][h] = dp[w][h-1] + dp[w-1][h+1]이 된다. 아래는 이를 구현한 코드이다. 생각보다 시간이 오래 걸린 문제였다. dp 문제를 더 많이 풀어봐야 겠다.

#include <iostream>

using namespace std;

int N;
long long dp[31][31];

void solution() {
    for (int i = 0; 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];
                continue;
            }

            dp[i][j] = dp[i][j - 1] + dp[i - 1][j + 1];
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    solution();

    while (1) {
        cin >> N;
        if (!N) break;
        cout << dp[N][0] << endl;
    }

    return 0;
}