2293번 동전1

  DP 문제를 오랜만에 풀려니 헷갈렸다.

 

 구해야하는 값을 k, 동전 갯수를 n이라고 할때 그 값을 dp[n][k]라고 표현하자. 주어진 예시처럼 n=3,k=10이라면 dp[10][3]라고 쓸 수 있다. dp[10][3]을 어떻게 구할 수 있을까? 반대로 생각해보면 된다. 마지막 1동전이 남았을때 dp[10-동전(1)][3], 2동전이 남았을때 dp[10-동전(2)][3], 동전3이 남았을때 dp[10-동전(3)][3]이라고 표현할 수 있고 이를 다 더하면 dp[10][3] 값이 된다.

 

 즉, dp[10][3]=dp[9][3]+dp[8][3]+dp[5][3]이라고 나타낼 수 있다. 이때 뒤의 배열 3개는 동전 갯수를 그냥 보여주기 위한 값이고 다시 정리하자면 dp[10] = dp[10-동전(1)]+dp[10-동전(2)]+dp[10-동전(5)]=dp[9]+dp[8]+dp[5] 이다.

 

 이를 토대로 점화식을 세우면 dp[k]+=dp[k-동전] 이고 이 식을 이용해 문제를 풀면 된다.

 

ps. Top-down 형식으로 풀어보려고 했지만 시간 제한때문에 Bottom-up을 사용하였다.