[DP-예제 2] 숫자 만들기

입력 N 과 M 이 주어지면, 1~M 까지 숫자를 더하여 N을 만드는 경우의 수를 구해보자.

5와 3 같은 경우는 1~3의 숫자를 임의로 골라 더해서 5를 만드는 경우의 수를 구하는 것이다.

숫자 1~3을 가지고 더해서 5를 만드는 경우의 수를 따지면 위와 같이 13가지가 나온다.

이제 문제를 해결하기 위해서 부분 문제를 정의해야 한다.

동적 계획법으로 기준을 세우기 위에서 마지막 숫자를 기준으로 3가지로 나눌 수 있다.

① 마지막에 숫자 1을 더하는 경우

② 마지막에 숫자 2를 더하는 경우

③ 마지막에 숫자 3을 더하는 경우

세분류로 나눈 것들이 뜻하는 것은 이렇게 해석 할 수 있다.

① 마지막에 숫자 1을 더하는 경우 -> 5에서 1을 뺀 나머지 부분에서 4를 만들어야 한다.

② 마지막에 숫자 2를 더하는 경우 -> 5에서 2을 뺀 나머지 부분에서 3를 만들어야 한다.

③ 마지막에 숫자 3을 더하는 경우 -> 5에서 3을 뺀 나머지 부분에서 2를 만들어야 한다.

즉 1~M 까지의 숫자를 더하여 N을 만드는 경우의 수는

마지막에 1이오는 경우 -> N에서 1을 뺀 (N-1)을 만드는 경우의 수

마지막에 2이오는 경우 -> N에서 1을 뺀 (N-2)을 만드는 경우의 수

마지막에 3이오는 경우 -> N에서 1을 뺀 (N-3)을 만드는 경우의 수

. . .

마지막에 M이오는 경우 -> N에서 M을 뺀 (N-M)을 만드는 경우의 수

를 모두 합치면 구할 수 있다는 뜻이다.

이제 문제를 이해 했으므로 절차를 따라 풀어야 한다.

T(i)를 1~M의 수를 이용하여 i을 만드는 경우의 수라고 정의하자.

M 이 3이고 i 가 4라고 가정하면 T(4) 는 위와 같이 7가지 경우의 수가 나온다.

점화식을 세우기 위해서 i 를 7로 가정하고 해석하면 위와 같다.

각각의 경우를 부분 문제로 정의하고,

점화식을 세우면 다음과 같은 식이 나온다.

마지막 단계로 코드를 작성하기 위한 과정이 남아 있다.

M=3 일 때, T(7) = T(6)+T(5)+T(4) 라는 식이 성립하고, 한 항을 구하기 위해서는

그 앞 세개의 항이 필요하다는 것을 알 수 있다. 

M=3 일 때, T(0) 은 1~3의 수를 더해 0을 만드는 경우의 수인데,

그러는 경우의 수는 없기 때문에 T(0)은 존재하지 않는다.

T(1) = 1, T(2) = 2 이다.

T(3) = 3 이지만 T(3)을 구하는 과정을 살펴보면 T(3) = T(2)+T(1)+1 이라는 것을 볼 수있다.

M 의 값이 어떤 값이 주어지는지 모르기 때문에, T(0)을 제외하고 T(1)부터 T(M) 까지를 일반화 시켜야 한다.

T(3) = T(2)+T(1)+1

T(2) = T(1)+1

T(1) = 1 

1부터 M까지의 항을 이렇게 일반화 할 수 있다. 그 다음에 초항을 이용하여 다음 항을 구하면 된다.

이것으로 동적 계획법 개념을 마무리 하겠다. 동적 계획법은 어떻게 보면 어려운 수학 문제를 푸는 것 같다고 느껴졌다.

하지만 절차에 따라 문제해결 방법을 알아내면 그 다음부터 코딩하는 것은 쉽다.

부분문제를 생각하고, 점화식을 세우고, 초항 또한 일반화 시켜야 하기 때문에

문제 풀이 방법을 생각해 내는 것이 매우 어렵고 신기했다.

블럭 채우기나 숫자 만들기 문제도 처음보면 어떻게 코드를 생각해야 할지 막막했지만

동적계획법으로 차근차근 해결 해 나가보니, 마지막에 코딩하는 양도 짧고, 단순했다.

출처 : Algorithm LABS