[백준] 2293 : 동전 1, 부분 문제의 해결(DP)

url : https://www.acmicpc.net/problem/2293

2293번: 동전 1

 

문제 해결을 위해 dp를 사용하는 이유

k원을 만드는 방법을 구하기 위해, k원보다 작은 금액을 만드는 방법이 반복적으로 계산된다.

=> 중복 계산을 피하기 위해 메모이제이션, Tabulation(미리 구하기)이 필요하다.

=> DP

 

2원 동전 사용을 고려할때, 4원을 만드는 경우의 수가 dp[4] = dp[4] + dp[4-2] 인 이유

DP에서 부분 문제의 해결 개념과 관련이 있다.

즉, 기존 경우의 수(dp[4])에서 2원 동전 하나를 사용하고 남은 2원을 만드는 방법을 더한다.

 

4원 만드는 경우의 수 = 기존 4원 만드는 경우의 수+ 2원을 사용해 4원 만드는 경우의 수

밑줄 친 부분을 보면 2원을 사용하고 나머지 금액을 만드는 경우의 수를 구할때(4-2=2원을 만드는 경우의 수)이전에 구한 dp[2]를 이용하여 구할 수 있다.

(여기서 dp[i]는 i원을 만드는 경우의 수이다.)

 

즉, 2원을 만드는 방법(부분문제의 해결)을 이용해 4원을 만드는 방법(전체 문제의 해결)을 구할 수 있다.