[Python] 프로그래머스. 거스름돈 (Level 3)

https://programmers.co.kr/learn/courses/30/lessons/12907

코딩테스트 연습 - 거스름돈 | 프로그래머스

풀이를 찾아보면 다들 전형적인 DP문제라고 하는데, 나한테는 왜 이렇게 어렵게 느껴졌는지 모르겠다.

 

점화식을

'table[y][x] = money[0] ~ money[y]까지의 동전으로 x원을 만드는 방법의 개수' 라고 정의하면

table[][]인 이차원 배열은

money 배열 원소의 개수 * 0원부터 n원까지의 금액(n+1개)

형태가 된다. 

 

금액 x원이 money[y]보다 클 때 새로운 경우의 수가 가능하고,

 

table[y+1][x]를 계산하기 위해서는 두 가지 생각을 해내야 한다.

1. 우선, money[0]부터 money[y]까지의 동전으로 x원을 만드는 방법은 그대로일 것이다.

2. money[y+1]원 동전이 추가되고 이 동전을 사용한다는 건, 전체 금액에서 이 동전 금액만큼의 차액을 money[0] ~ money[y+1] 동전으로 만들어내는 것과 같다.

 

예컨대 동전 [1]원이 주어진 채 만들어야 하는 액수가 4원이면, 여기에 2원 동전을 추가할 경우

[1,2]원으로 4원 만드는 방법 = 1원만으로 4원 만드는 방법 + 2원을 사용하고, 남은 차액 2원 (4 - 2원)을 1원으로 만드는 방법

이 된다.

 

점화식으로 표현하면

table[y][x] = table[y-1][x] + table[y][x - money[y]] 가 된다.