백준 알고리즘, 2225 문제

---

풀이

0 ~ 20 까지 3 개를 더한다고 생각해보자.

1. 0 + ( 0 ~ 20 까지 2개를 더하는 방법의 수 )

2. 1 + ( 0 ~ 19 까지 2개를 더하는 방법의 수 )

3. 2 + ( 0 ~ 18 까지 2개를 더하는 방법의 수 )

...

위 방법을 고안해냈다.

DP 배열을 어떻게 표현할지 고민했다.

DP[N][K] = 0 ~ N 까지 K 개를 더하는 방법의 수

이제 for 문으로 값을 만들어나가야 하는데,

위 방식에서 분홍색을 선택할 경우 3 중 for 문이 필요할 것이고

연두색 방법을 선택할 경우 2 중 for 문이면 해결이 된다.

---

코드

@github 에서 확인하기

/**
 * @site: https://www.acmicpc.net/problem/2225
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 14
 */
#include <iostream>
using namespace std;
int main() {
    int DP[201][201] = {0,};
    int N, K, i, j;
    cin >> N;
    cin >> 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][j - 1] % 1000000000) + (DP[i - 1][j] % 1000000000);
        }
    }
    cout << (DP[N][K] % 1000000000) << endl;
    return 0;
}