[백준][C++/Python] 2225번: 합분해 (254)

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

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

2225번: 합분해

 

생각의 흐름

솔직하게 이거 나는 DP인거 생각 못했다. 그냥 BFS로 완전탐색 해야 하나? 이런 생각부터 들었던것이 사실이다.

해결방법이 딱 떠오르지 않아 다른 분들의 글을 좀 읽어본 후에서 야 DP임을 깨닫고 풀이방법을 읽어보게 되었다.

​

우선 DP배열을 정의해야 한다. DP[a][b] 는 숫자 a개로 합이 b가 되는 경우 를 의미한다.

​

DP[3][6] 을 구해야 한다고 가정해보자.

이러한 경우의 수 들중에서 끝이 0으로 끝나는 배열부터, 끝이 6으로 끝나는 배열까지 존재할 것 이다.

만약 끝이 0으로 끝난다면 이는 사실상 DP[2][6]에서의 경우의 수와 동일하다.

만약 끝이 1로 끝난다면 이는 사실상 DP[2][5]에서의 경우의 수와 동일하다.

이러한 모든 DP[2][?]에 해당하는 경우의 수드을 합하면 DP[3][6]에 해당하는 경우의 수를 구할 수 있다.

참고로 변수 long long으로 잡아야 한다. 이점을 생각하지 못해서 3번이나 틀렸다... 이는 실수가 아닌 실력이 부족함을... 윽....

(ps, 파이썬은 이런거 생각 안해서 개꿀이긴 하다...)

 

나의 코드

1) C++

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1000000000;

long long DP[201][201];

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	int N, K;
	cin >> N >> K;
	
	for(int i = 0; i <= N; i++){
        DP[1][i] = 1;
    }

    for(int i = 2; i <= K; i++){
        for(int j = 0; j <= N; j++){
            for(int k = 0; k <= j; k++){
                DP[i][j] += (DP[i-1][j-k] % MOD);
            }
        }
    }

    cout << DP[K][N] % MOD;	
	

    return 0;
}

 

2) Python

import sys

MOD = 1000000000

N, K = map(int, sys.stdin.readline().split())
DP = [[0 for _ in range(N+1)] for _ in range(K+1)]

DP[0][0] = 1
for i in range(1, K + 1):
    for j in range(0, N + 1):
        for k in range(0, j+1):
            DP[i][j] += DP[i - 1][j - k]
        DP[i][j] %= MOD

print(DP[K][N] % MOD)