[DP] 백준 문제 풀이 - 2225 합분해

👩🏻‍💻 문제링크

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

2225번: 합분해

 

✍️ 아이디어

1. 문제 이해

• 0~N까지 정수 K개를 더해서 그 합이 N이 나오는 경우의 수를 구하자

2. 점화식 D[N][K] = 0~N까지 정수 K개를 더해서 그 합이 N이 나오는 경우의 수 

3. ex) 6까지 정수 4개를 더해서 합이 6 = 6까지 정수 3개를 더해서 + 5까지 정수 3개를 더해서 + 4까지 정수 3개를 더해서 .....+ 0까지 정수 3개를 더해서 (이 아이디어는 내가 직접 떠올림 !)

 

4. 처음에 n=0, k=0~200 의 값이 1이라는 점을 간과함 

✍️소스코드

• 내 코드

#include <iostream>
using namespace std;
long long result[201][201];

int main()
{
	int n; cin>>n;
	int k; cin>>k;
	
	for(int i=0; i<200; i++) // 이걸 간과함;;
	{
		result[0][i]=1;
	}

	
	for(int i=1; i<=n; i++)
	{
		for(int j=1; j<=k; j++)
		{
			for(int p=0; p<=i; p++)
			{
				result[i][j]+=result[p][j-1];
				result[i][j]%=1000000000;
			}
		}
	}
	cout<<result[n][k]<<'\n';
}

 

=> 처음에 result[0][k]를 생각 안해서 시간이 오래걸렸다

 

 

• 다른 사람의 코드 (내것과 배열에 저장한 값이 다름)

#include <iostream>
using namespace std;
 
int main(int argc, const char * argv[]) {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    int N, K;
    int dp[201][201] = {0};//dp[K][N] => K개로 N만들기
    
    cin >> N >> K;
    
    for(int i = 0; i <= N; i++){
        dp[1][i] = 1;
        dp[2][i] = i + 1;
    }
    
    for(int i = 3; i <= K; i++){
        for(int j = 0; j <= N; j++){
            for(int k = 0; k <= j; k++){
                dp[i][j] = (dp[i][j] + dp[i-1][j-k]) % 1000000000;
            }
        }
    }
    cout << dp[K][N] << '\n';
    
    return 0;
}

 

체감난이도	걸린시간	참고	사용 문법
중상	1hour	다른사람 풀이	벡터 정렬