[C++] 백준 2225번 : 합분해 (G5)

#문제

www.acmicpc.net/problem/2225

2225번: 합분해

#풀이 & 학습한 내용

dp배열은 long long으로 선언했지만, sum을 int로 선언하여 "틀렸습니다"가 나왔다. int의 최댓값 약 2,000,000,000을 기억하자. 합하는 과정에서 int의 범위를 넘을 수 있으므로 sum도 long long으로 선언해주어야 한다. 또한 모듈로 법칙인 (A+B)%C=(A%C+B%C)%C 또한 잊지말자. dp[i][j]를 "0~i까지의 정수 j개를 더해 i를 만드는 경우의 수"라 하고, dp[30][3]과 같은 경우를 예로 들어 dp배열을 어느순서로 채울지 먼저 파악한다. 그리고 그 순서에 맞게 for문을 구성하여 dp배열을 dp[N][K]까지 채운다.

 

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
long long dp[201][201];
 
int main(void) {
    int N, K;
    cin >> N >> K;
 
    for (int i = 0; i <= N; i++) {
        dp[i][1] = 1;
    }
    for (int j = 2; j <= K; j++) {
        for (int p = 0; p <= N; p++) {
            long long sum = 0;
            for (int i = 0; i <= p; i++) {
                sum += dp[i][j - 1] % 1000000000;
            }
            dp[p][j] = sum % 1000000000;
        }
    }
    cout << dp[N][K] << '\n';
 
}