boj 11560 다항식 게임

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

 

약 1년만에 dp 문제입니다. 그동안 게을러 빠졌었네요 ^^..

 

이 문제는 N, M의 범위가 작으므로 미리 모든 값을 구할 수 있습니다.

그 다음 입력받는대로 출력만 하면 되는 방식입니다.

 

우선 점화식은 N을 직접 늘려가면서 다항식을 구해보시면 충분히 나올 수 있습니다.

 

여기서 알 수 있는 점화식은

i번째 다항식의 j번 계수는 [i - 1번째 다항식]의 [j - i번째 계수] ~ [j번째 계수]까지의 합으로 구할 수 있습니다.

그렇다면 점화식은

dp[i][j] = dp[i - 1][j - i] + dp[i - 1][j - i + 1] + ... + dp[i - 1][j]

이렇게 될 것이고, 코드로 그대로 옮겨주시면 되겠습니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX_N 21
#define MAX_M 211
using namespace std;
typedef long long ll;
 
ll dp[MAX_N][MAX_M];
int N, M;
 
void init() {
    dp[1][0] = 1LL;
    dp[1][1] = 1LL;
    for (int i = 2; i < MAX_N; i++) {
        for (int j = 0; j <= (i * (i + 1)) >> 1; j++) {
            for (int k = max(0, j - i); k <= j; k++) {
                dp[i][j] += dp[i - 1][k];
            }
        }
    }
}
 
void func() {
    cout << dp[N][M] << '\n';
}
 
void input() {
    cin >> N >> M;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
 
    int tc;
    cin >> tc;
    while (tc--) {
        input();
        func();
    }
 
    return 0;
}