프로그래머스 Lv.3 - 거스름돈 (DP) Python

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

해당 문제는 각 돈의 종류로 특정 값을 만들 수 있는 모든 경우의 수를 출력하는 문제다.

이 또한 지난 포스팅과 같이 다이나믹 프로그래밍으로 풀이가 가능하다.

 

즉 위 문제 예시와 같이, n = 5원 / money = [1,2,5]라면

리스트 money에 있는 동전으로 만들 수 있는 0원 ~ 5원까지의 경우의 수를 구해나가며 5원을 만들 수 있는 경우의 수를 구할 수 있다.

 

먼저 경우의 수를 담을 리스트를 선언한다.

이때, 앞서 언급한 것과 같이 0원 ~ 5원을 만들 수 있는 경우의 수를 담아야 하므로 리스트의 길이는 n+1 이고 초깃값은 0이다.

하지만, 0원을 만드는 경우는 '모든 돈을 사용하지 않는 경우' 뿐이므로, dp[0]은 1 로 수정한다.

dp = [0] * (n+1)
dp[0] = 1

 

그리고 이 문제를 어떤 식으로 해결하면 좋을지 표를 먼저 그린 뒤 쪼개어 생각해본다.

인덱스	0원	1원	2원	3원	4원	5원
1원	X	(1)	(1,1)	(1,1,1)	(1,1,1,1)	(1,1,1,1,1)
1원 + 2원	X	X	(2)	(2,1)	(2,2), (2,1,1)	(2,2,1), (2,1,1,1)
1원 + 2원 + 5원	X	X	X	X	X	(5)
경우의 수	1	1	2	2	3	4

1원과 2원으로 1원을 만드는 방식은 1원을 하나 사용하는 한가지가 존재한다. (1)

1원과 2원으로 2원을 만드는 방식은 1원을 두 개 사용하는 방식과, 2원을 하나 사용하는 방식이 존재한다. (1,1), (2)

이때 2원을 만들기 위해, 1원을 만드는 방식인 (1)에서 1원을 또 추가한 방식인 (1,1)로 2를 만들 수 있고,

최소 2원을 만들기 위해서, 2원을 사용할 수 있으므로 (2)를 만들 수 있다는 사실을 알 수 있다.

 

그리고 더 나아가 3원을 만들 때는 2원을 만드는 방식에서 1원을 추가하여 (1,1,1),

1원을 만드는 방식에서 2원을 추가하여 (1,2)을 만들 수 있다.

즉 3원을 만드는 경우의 수는

(3-'1')원을 만드는 경우인 (1,1)에 '1'원을 더하는 경우와,

(3-'2')원을 만드는 경우인 (1)에 '2'원을 더하는 경우의 합이다.

즉, n이 m을 포함한 경우의 수를 구하기 위해서는 n - m 을 만드는 경우에서 참조해야 한다.

 

이를 활용하여 전체 코드를 작성하면 다음과 같다.

def solution(n, money):
  money.sort()
  dp = [0] * (n+1)
  dp[0] = 1
  
  for coin in money :
    for i in range(coin, n+1) :
      dp[i] += dp[i-coin]

  return dp[n]