[Java] 다이나믹 프로그래밍 (동전 1)

일부러 DP만 푸는 게 아니라 풀어보니 DP였다.

 

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

2293번: 동전 1

 

해당 문제는 쉽게 점화식을 떠올릴 수 있는데 중복을 허락하지 않는다는 부분에서 고민이 길어졌다.

10원을 만들기 위해서는 dp[10] = dp[9] + dp[8] + dp[5] 처럼 제안된 동전의 값어치만 더하면 10원이 되는 식으로 점화식을 세울 수 있다.

 

하지만 이 문제는 중복을 허락하지 않는다.

예를 들어 만약 1과 2로 4를 만들어야할 때,

1+1+1+1 = dp[4-1=3] 에 저장

2+1+1     = dp[4-1=3] 에 저장

2+2         = dp[4-2=2] 에 저장

 

이런 식으로 3가지 경우를 생각할 수 있어서 dp[4] = dp[3]+dp[2]로 생각했지만 dp[2]에 1+1+2 또한 저장되어 있어 답이 아니다. 

 

이 문제는  K를 돌면서 N을 돌면 구성을 구분하지 않는 경우의 수가, N을 돌면서 K를 돌면 구성을 구분하는 경우의 수가 나온다. 즉 for문을 도는 순서에 따라 중복이 허락여부가 결정된다. 왜 그런지는 집중해서 생각해보면 그럴것 같다.

 

아무튼 dp문제에서 중복에 대한 내용이 나오면 for문 도는 순서를 바꿔보자