[BOJ] 2225. 합분해(DP)

#. Problem

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

* The copyright in this matter is in BOJ

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

먼저

20 2 이 입력되었을 때, 출력이 21이 되려면

아래와 같은 경우가 있다.

20 0

19 1

18 2

...

2 18

1 19

0 20

DP식을 세워보면 

DP[N][K]로 세울 수 있다.

N이 0일 때,

0을 만들 수 있는 방법은 0을 더하는 방법뿐이다.

K = 1,     0     (1)

K = 2,     0+0    (1)

K = 3,     0+0+0    (1)

...

N이 1일 때,

K = 1,     1    (1)

K = 2,     1+0,     0+1    (2)    

K = 3,     1+0+0,     0+1+0,    0+0+1    (3)

...

N이 2일 때,

K = 1,     2    (1)

K = 2,     1+1,     2+1,    1+2    (3)

K = 3,     0+0+2,     0+2+0,    2+0+0,     1+1+0,    1+0+1,    0+1+1    (6)

...

이정보면 점화식이 보일 것 같다.

DP[3][4] = DP[2][4] + DP[3][3]

DP[N][K] = DP[N-1][K] + DP[N][K-1]

#. Code

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

#include <cstdio> using namespace std; #define mod 1000000000   int DP[201][201];   int main(void) {     int n, k, i, j;     scanf("%d %d", &n, &k);       for (i = 1; i <= k; i++)         DP[0][i] = 1;       for (i = 1; i <= n; i++)          for (j = 1; j <= k; j++)              DP[i][j] = (DP[i - 1][j] + DP[i][j - 1]) % mod;              printf("%d\n", DP[n][k]);       return 0; } Colored by Color Scripter

cs

line 13) 직관적인 작은 문제를 먼저 구해준다.

line 17) 점화식 적용!

#. Other Code

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 28

/* reference : hansc0320 */   #include <stdio.h> #include <string.h> #include <algorithm>   #define MOD (int)1e9   using namespace std;   int N, K, D[201];   int main(void) {     scanf("%d %d", &N, &K);       D[0] = 1;       for (int i = 1; i <= K; i++)         for (int j = 1; j <= N; j++)             D[j] = (D[j - 1] + D[j]) % MOD;       printf("%d\n", D[N]);       return 0; } Colored by Color Scripter

cs

일차원 배열을 사용해서 메모리가 더 효율적이다.