백준 2225 합분해 쉬운 풀이

문제링크 : https://www.acmicpc.net/problem/2225

문제 접근

• 감이 안오는데? 각 케이스를 생각해보자

  • 20 = 19 + 1, 18+2, 17+3
  • 만약 K가 3일경우엔, 20 = 18+1+1, 17+1+2, 17+2+1, ...
  • 이전 값을 다시 재활용해서 사용할 수 있을것 같음 >> DP로 해보자 >> 종류 2차원 DP 문제
    • DP[K][N] = K개를 사용해서 N을 구하기 위해서 경우의 수
  • 앞에는 1개로 정해놓고 뒤에만 움직이는경우
    • DP[K][N] = DP[1][0] +DP[K-1][N] + DP[1][1] + DP[K-1][N-1] + DP[1][2] + DP[1][K-2] + ...
  • 근데 어짜피 K가 1이면 DP[1][K] = 1
  • DP[K][N] = DP[K-1][0] + DP[K-1][1] + DP[K-1][2] + ...DP[K-1][N]
  • 이때 예외가 있을까?
    • K = 1일때는 적용 안됨, 항상 종류 1
      ### 시간복잡도 계산

• DP[N][K]에서 연산횟수 >> N-1번, 약 N번이라고 가정시

  • O(N_K_N) = O(N^2 * K) = 8e6 >> 가능
    ### 인트 계산

• dp값을 1e9 나머지로 계산해줘서 신경써줄 필요없음
  ### 코드

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

  #include <iostream>   using namespace std; int dp[210][210]; int main() {     int N,K;     cin >> N >> K;     fill(&dp[0][0], &dp[209][210], 0);     dp[0][0]= 1;     // K=1 일경우 경우의수 1개 >> 각 수를 내서 만들수 있으니까     fill(&dp[1][0], &dp[1][210], 1);          for(int j=2; j<=K; j++) {         for(int i=0; i<=N; i++) {             for(int k=0; k<=i; k++) {                 dp[j][i] = (dp[j][i] + dp[j-1][k]) % 1000000000;             }                      }     }          cout << dp[K][N] << '\n';               return 0; }   Colored by Color Scripter

  cs

문제유형

• DP - 이전 종류값 만을 포함
  • dp[N][K] = N개의 종류를 가지고있을때, K가치를 가질때의 dp 값
  • 단, 이전값만을 활용하는경우, dp[N]으로 줄여서 사용할 수 있음
    • 단 한번만 빼줘야함, 뺀곳에 여러번 뺀 경우의 수가 담겨있음
  • 대표문제 : knapsack
    • 여러 종류의 아이템을 한번씩 넣을수있을때, 한정된 비용에서의 최대가치 구하는 문제
    • dp[N][K] : N개의 종류를 들고, K만큼의 무게에서의 가질수 있는 최대 가치
    • https://www.acmicpc.net/problem/12865

비슷한 문제

• https://www.acmicpc.net/problem/2293
• https://www.acmicpc.net/problem/2294
• https://www.acmicpc.net/problem/2225
• https://www.acmicpc.net/problem/12865