BOJ#2225 합분해

BOJ#2225 합분해

* 문제

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

* 풀이

dynamic Programming 문제입니다.

예를 들어 2 2가 입력된 경우 아래와 같이 3가지 경우가 있을 수 있습니다.

0 + 2

1 + 1

2 + 0

3 2가 입력된 경우에는

0 + 3

1 + 2

2 + 1

3 + 0

4 2가 입력된 경우에는

0 + 4

1 + 3

2 + 2

3 + 1

4 + 0

감이 오시나요?

어떻게 풀어야 할지 모를때는 예제의 숫자를 낮춰서 생각하면 좋습니다.

" N K가 입력된 경우에서

첫번째 숫자가 m으로 정해지면

나머지는 N-m K-1의 경우가 됩니다. "

dp를 아래와 같이 정의하고 위 내용을 구현하시면 되겠습니다.

 - dp[N][K] : 0~N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수

---

* 나의 코드

https://github.com/stack07142/BOJ/tree/master/BOJ%232225_SumDecomposition