[BOJ/백준] 2225 합분해

● [문제번호 2225] 합분해

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

2225번: 합분해

 

● 알아야 할 것

: 다이나믹 프로그래밍

 

● 풀이 과정

: 알고리즘 기초 1/2 - 400 다이나믹 프로그래밍1 에 있던 문제이다.

 

: 풀이를 떠올리다가 중복조합으로 풀면 되겠다고 생각했으나

계산과정을 어떻게 해야할지 의문이어서 구글링했다가

다른 방법으로 풀어야한다는 것을 알았다.

 

: DP 풀이과정 (Bottom - Up)

1. 테이블 정의하기

→ dp[k][n] : k개의 정수를 합하여 n을 만들수 있는 경우의 수

 

2. 점화식 찾기

→ dp[K][N] = dp[K - 1][0] + dp[K - 1][1] + ... dp[K - 1][N - 1] + dp[K - 1][N]

 

3. 초기값 정하기

→ 1개의 정수로 n을 만드는 경우의 수는 1이다.

dp[1][n] = 1

(1 ≤ n ≤ N)

 

 

● 주의 할 것

: 각 계산 완료된 값의 나머지 연산을 적용해야 나중에 long long의 범위를 넘어가는 일이 없다.

 

● 참고 할 것

: 풀이과정

https://lmcoa15.tistory.com/64

 

 

● 풀이 코드

#include <bits/stdc++.h>

using namespace std;

// dp[k][n] : k개의 정수를 합하여 n을 만들수 있는 경우의 수
long long dp[201][201];
int N, K;

void program()
{
    // 초기값 설정
    for(int n = 0; n <= N; n++)
        dp[1][n] = 1;
    
    // 점화식
    for(int k = 2; k <= K; k++)
    {
        for(int n = 0; n <= N; n++)
        {
            for(int index = 0; index <= n; index++)
                dp[k][n] += dp[k - 1][index];
            
            // 각 계산 완료된 값의 나머지 연산 적용
            dp[k][n] %= 1000000000;
        }
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N >> K;
    
    program();
    
    cout << dp[K][N];
    
    return 0;
}

 

 

● [백준] - [알고리즘 기초 1/2] - [402 - 다이나믹 프로그래밍 1 (도전)] 문제집

번호	문제 번호	문제 이름	풀이 링크
1	1309	동물원	https://pirateturtle.tistory.com/255
2	2225	합분해	https://pirateturtle.tistory.com/256
3	17404	RGB거리 2	https://pirateturtle.tistory.com/257