[백준/C++] 2225번_합분해

문제는 다음과 같습니다.

점화식을 세우는 데까지 가 어려운 문제인 것 같습니다. ㅠㅠ
dp문제이고 점화식을 세워야하는 걸 아니까 점화식을 어떻게든 세우게 되네요,,

먼저 저는 dp[n][k] 인 2차원 배열을 이용했습니다.
이때 이 의미는,

dp[n][k]: 0부터 n까지의 정수 k개를 더하여, 그 합이 n이 되는 경우의 수

계단문제나, 어떤 dp문제이든 일반적인 i번째 경우를 보고
마지막에 오는 수를 기준으로 생각하라고 했습니다-

즉, dp[n][k]에서 마지막에 오는 수를 i라고 했을 때,
dp[n][k] = 숫자i + dp[n-i][k-1] 이 됩니다.
그리고 이 숫자i는 0부터 n까지가 가능합니다. (0<=i<=n)

즉, dp[n][k] = Σ(i = 0~n까지) dp[n-i][k-1] 이 됩니다.

dp[n][k] = Σ(i = 0~n) dp[n-i][k-1]

---

n은 0부터 가능하므로, 이를 0부터 입력받은 n까지 buttom-up 방법으로 구하면 됩니다.
입력받은 n, k를 각각 변수 i, j 로 놓고 buttom-up으로 구하는 반복문은 다음과 같습니다.

    for(int i=0; i<=n; i++){
      for(int j=1; j<=k; j++){
        for(int t=0; t<=i; t++){ // 마지막 수가 t로 끝났을 때
          dp[i][j]+=dp[i-t][j-1]; // 0~i까지의 수 j개를 더하여 합이 i가 되는 경우
          dp[i][j]%=1000000000;
        }
      }
    }

또한, 맨 처음에 초기화해주는 부분에서는
숫자 n을 수 1개만 이용해서 표현하는 경우의 수는 자기자신 n으로 표현하는 1가지 이므로, dp[i][1]=1로 초기화를 하였고
숫자 n을 수 0개만 이용해서 표현하는 경우의 수는 0개이므로,
dp[i][0]=0으로 세팅하였습니다.

전체 코드는 다음과 같습니다.

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k; long long dp[201][201]={0, };
    cin>>n>>k;

    for(int i=0; i<=n; i++){
      dp[i][1]=1;
      dp[i][0]=0;
    }

    for(int i=0; i<=n; i++){
      for(int j=1; j<=k; j++){
        for(int t=0; t<=i; t++){ // 마지막 수가 t로 끝났을 때
          dp[i][j]+=dp[i-t][j-1]; // 0~i까지의 수 j개를 더하여 합이 i가 되는 경우
          dp[i][j]%=1000000000;
        }
      }
    }
    
    cout<<dp[n][k]<<endl;
    return 0;
}

---

2월 8일 화요일 복습)

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long dp[201][201]={0, };
    long long mod=1000000000;
    int n, k; cin>>n>>k;

    dp[0][0]=1;

    for(int i=0; i<=n; i++){
      for(int j=1; j<=k; j++){ // j는 1~k개 (나타낼 수 있는 개수)
        for(int t=0; t<=i; t++){ // t는 마지막 수
          dp[i][j]+=(dp[i-t][j-1]%mod);
        }
        dp[i][j]%=mod;
      }
    }

    cout<<dp[n][k]<<"\n";
    return 0;
}