[Python] 프로그래머스 Lv3_거스름돈

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

프로그래머스

 

• 손님들께 거스름돈 n 원을 줄 때 방법의 경우의 수 구하기
• ex) 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 주기 가능
  • 1) 1원을 5개 사용
  • 2) 1원을 3개 사용하고, 2원을 1개 사용
  • 3) 1원을 1개 사용하고, 2원을 2개 사용
  • 4) 5원을 1개 사용
• n: 거슬러 줘야 하는 금액
• money: Finn이 현재 보유하고 있는 돈의 종류
• Finn이 n 원을 거슬러 줄 방법의 수를 return

제한 사항

• n은 100,000 이하의 자연수
• 화폐 단위는 100종류 이하
• 모든 화폐는 무한하게 있다고 가정
• 정답이 커질 수 있으니, 1,000,000,007로 나눈 나머지를 return

 

"""
입출력 예시)

n = 5, money = [1,2,5] -> 4
"""

 

 

## 의사코드 ##

# DP -> 점화식 찾기

# 제일 작은 화폐부터 사용

# 빈 리스트 생성
# dp = [0] * n+1

# money 내에서 반복
# for coin in money:
#   현재 선택한 coin으로 n원 이하까지의 금액(price)을 만들 수 있는 경우의 수를 dp에 저장
#   for price in range(coin, n+1): # coin ~ n까지 반복
#       if price >= coin: # price가 coin보다 작은 경우는 없음
#           dp[price] += dp[price - coin] # dp[price] = (price - coin)원을 만들 수 있는 경우 각각에 coin을 더한 것

# 1,000,000,007로 나눈 나머지를 return
# return dp[n] % 1,000,000,007

 

 

 

통과한 코드

 

def solution(n, money):
    # 빈 리스트 생성
    dp = [0] * (n+1)
    # 초기값 설정
    dp[0] = 1
    for coin in money:
        for price in range(coin, n+1):  # coin ~ n까지 반복
            if price >= coin: # price가 coin보다 작은 경우는 없음
                dp[price] += dp[price - coin] # dp[price] = (price - coin)원을 만들 수 있는 방법 각각에 coin을 더한 것
    return dp[n] % 1000000007

-> 제일 작은 화폐부터 사용해서 해결하고, 그 값을 다음 큰 화폐를 사용할 때 재활용하므로 DP(동적 계획법) 이용

 

! dp[0]을 1로 설정하지 않으면 dp[price]가 업데이트되지 않음 !

 

 

• 'dp[price] = (price - coin)원을 만들 수 있는 경우 각각에 coin을 더한 것'의 의미

# money = [1, 2, 5]일 때 coin: 2, price: 4 인 경우
# => 1) 1+1+1+1
# => 2) 1+1+2
# => 3) 2+2

# 현재 dp[4] = 1 
# -> coin: 1, price: 4 일 때 갱신된 값
# => 1+1+1+1

# price - coin: 2, dp[2] = 2
# => 1) 1+1
# => 2) 2

# dp[price] + dp[price - coin]
# => dp[4] + dp[4-2] = 1 + 2 = 3
#     -> dp[4]: coin: 1, price: 4 일 때의 값으로 1원 동전만으로 4원을 만드는 경우의 수
#         => 1) 1+1+1+1
#     -> dp[4-2]: 1원 동전과 2원 동전으로 2원을 만드는 경우의 수  
#         => 1) 1+1
#         => 2) 2

# 'dp[price] = (price - coin)원을 만들 수 있는 경우 각각에 coin을 더한 것'의 의미
# -> (4-2)원을 만들 수 있는 방법 각각에 coin(2)을 더한 것
#     => 1) (1+1) + 2
#     => 2) (2) + 2

 

 

• 전체 코드 과정 확인

"""
coin: 1
price: 1
dp[1]('dp[price]'): 0
dp[0]('dp[price - coin]'): 1
갱신된 dp[1]('dp[price] += dp[price - coin]'): 1 

coin: 1
price: 2
dp[2]('dp[price]'): 0
dp[1]('dp[price - coin]'): 1
갱신된 dp[2]('dp[price] += dp[price - coin]'): 1 

coin: 1
price: 3
dp[3]('dp[price]'): 0
dp[2]('dp[price - coin]'): 1
갱신된 dp[3]('dp[price] += dp[price - coin]'): 1 

coin: 1
price: 4
dp[4]('dp[price]'): 0
dp[3]('dp[price - coin]'): 1
갱신된 dp[4]('dp[price] += dp[price - coin]'): 1 

coin: 1
price: 5
dp[5]('dp[price]'): 0
dp[4]('dp[price - coin]'): 1
갱신된 dp[5]('dp[price] += dp[price - coin]'): 1 

coin: 2
price: 2
dp[2]('dp[price]'): 1
dp[0]('dp[price - coin]'): 1
갱신된 dp[2]('dp[price] += dp[price - coin]'): 2 

coin: 2
price: 3
dp[3]('dp[price]'): 1
dp[1]('dp[price - coin]'): 1
갱신된 dp[3]('dp[price] += dp[price - coin]'): 2 

coin: 2
price: 4
dp[4]('dp[price]'): 1
dp[2]('dp[price - coin]'): 2
갱신된 dp[4]('dp[price] += dp[price - coin]'): 3 

coin: 2
price: 5
dp[5]('dp[price]'): 1
dp[3]('dp[price - coin]'): 2
갱신된 dp[5]('dp[price] += dp[price - coin]'): 3 

coin: 5
price: 5
dp[5]('dp[price]'): 3
dp[0]('dp[price - coin]'): 1
갱신된 dp[5]('dp[price] += dp[price - coin]'): 4 
"""

 

 

 

참고)

 

https://velog.io/@younge/Python-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-%EA%B1%B0%EC%8A%A4%EB%A6%84%EB%8F%88-%EC%97%B0%EC%8A%B5%EB%AC%B8%EC%A0%9CDP

[Python] 프로그래머스 - 거스름돈 (연습문제/DP)