Posts 거스름돈[Python]
Post
Cancel

거스름돈[Python]

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

문제 설명

  • Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.
  • 예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.
    1
    2
    3
    4
    
    1원을 5개 사용해서 거슬러 준다.
    1원을 3개 사용하고, 2원을 1개 사용해서 거슬러 준다.
    1원을 1개 사용하고, 2원을 2개 사용해서 거슬러 준다.
    5원을 1개 사용해서 거슬러 준다.
    
  • 거슬러 줘야 하는 금액 n과 Finn이 현재 보유하고 있는 돈의 종류 money가 매개변수로 주어질 때, Finn이 n 원을 거슬러 줄 방법의 수를 return 하도록 solution 함수를 완성해 주세요.

제한 사항

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

문제 풀이

  • 금액이 다른 동전이 주어질때 주어진 금액 n이 되는 경우의 수를 구하는 문제
  • 각 동전별로 금액을 계산할 수 있는 경우의 수를 구하면 된다.
  • dp로 풀면됨
  • 가장 금액이 작은 동전으로 구할 수 있는 경우의 수는 금액에 따라서 각 1개씩만 존재함
  • 그 다음으로 큰 동전에 대한 경우의 수는 이전에 구한 경우의 수를 합산해주면 됨.
  • 출처 : https://dirmathfl.tistory.com/191
1
2
3
4
5
6
7
8
def solution(n, money):
    dp = [1] + [0] * n
    
    for coin in money:
        for price in range(coin, n + 1):
            if price >= coin:
                dp[price] += dp[price - coin]
    return dp[n] % 1000000007
1
2
3
n = 5
money = [1, 2, 5]
solution(n, money)
1
4
This post is licensed under CC BY 4.0 by the author.

점프와 순간이동 [Python]

문자열 압축[Python]

Comments powered by Disqus.