[프로그래머스][level3] 거스름돈 -python

문제 링크

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

코딩테스트 연습 - 거스름돈

 

dp 개념 복습

 

• 다이나믹 프로그래밍이란 ? 큰 문제를 작게 나누고, 같은 문제라면 한 번씩만 풀어 문제를 효율적으로 해결하는 알고리즘
• 조건
  • 큰 문제를 작은 문제로 나눌 수 있다.
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다 
  • 예 ) 메모제이션(캐싱) : 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법

 

풀이 - 다른 블로그 참고

 

dp 문제라고 생각은 했는데, 점화식 도출을 못해서 다른 블로그 글을 참고했다. 설명을 읽어도 이해를 하는데 좀 오래걸렸다.

 

• 메모제이션을 통해, 동전에 따라 발생하는 경우의 수를 구한다. 
• answer[price] += answer[price-coin] 이다. 
• 예 ) n = 5, money = [ 1,2,5 ] 라고 하자.
  • n+1 만큼 메모할 answer 리스트를 만든다. answer의 각 인덱스의 수를 각 동전으로 만들 수 있는 경우의 수를 메모한다. 
  • 먼저, 동전 1원로 메모했을 때 : [ 1, 1, 1, 1, 1, 1 ]
  • 동전 2원로 메모했을 때 : [ 1, 1, 2, 2, 3, 3 ]

왜냐하면, 2번 인덱스는 1,2원으로 거스름원 2원을 만들 수 있는 경우의 수이다. 따라서 1원만으로 2원을 만들 수 있는 경우의 수 + 1원만으로 0(price-coin)원을 만들 수 있는 경우의 수 

3번 인덱스는 1, 2원으로 거스름돈 3원을 만들 수 있는 경우의 수이다. 따라서 1원만으로 3원을 만들 수 있는 경우의 수 + 1원만으로 1(price-coin)원을 만들 수 있는 경우의 수 

4번 인덱스는 1,2원으로 거스름돈 4원을 만들 수 있는 경우의 수이다. 따라서 1원만으로 4원을 만들 수 있는 경우의 수 + 1원과 2원만으로 2(price-coin)을 만들 수 있는 경우의 수 

5번 인덱스는 1,2원으로 거스름돈 5원을 만들 수 있는 경우의 수이다. 따라서 1원만으로 5원을 만들 수 있는 경우의 수 + 1원과 2원만으로 3(price-coin)을 만들 수 있는 경우의 수 

       

• 동전 5원으로 메모했을 때 : [ 1, 1, 2, 2, 3, 4 ]

왜냐하면, 5번 인덱스는 1,2,5원으로 거스름돈 5원을 만들 수 있는 경우의 수이다. 따라서 1원, 2원만으로 5원을 만들 수 있는 경우의 수 + 1원만으로 0(price-coin)원을 만들 수 있는 경우의 수 

 

• 메모제이션을 통해 구한 결과를 메모해두고 메모한 결과를 그대로 가져온다. 
• 풀이 과정을 쓰면서도 계속 헷갈렸다..

def solution(n, money):

  answer = [0] * (n+1)

  answer[0] = 1

  for coin in money:
    for price in range(coin, n+1):
      answer[price] += answer[price-coin]
  
  return (answer[n]) % 10000000007