본문 바로가기
알고리즘

프로그래머스 거스름돈 (python, 파이썬)

by 블쭌 2021. 1. 31.
728x90
  • 문제

Finn은 편의점에서 야간 아르바이트를 하고 있습니다. 야간에 손님이 너무 없어 심심한 Finn은 손님들께 거스름돈을 n 원을 줄 때 방법의 경우의 수를 구하기로 하였습니다.

예를 들어서 손님께 5원을 거슬러 줘야 하고 1원, 2원, 5원이 있다면 다음과 같이 4가지 방법으로 5원을 거슬러 줄 수 있습니다.

  • 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 money result
5 [1,2,5] 4

  • 코드
def solution(n, money):
    # dp생성
    dp = [[0]*(n+1) for _ in range(len(money))]
    
    # 0원은 지불 가능하니까 1로 시작
    dp[0][0] = 1
    
    # 첫번째 금액으로 n원을 구성 가능하면 1로 변경
    for i in range(money[0], n+1, money[0]):
        dp[0][i] = 1
    
    # y: 지불가능한 동전
    for y in range(1, len(money)):
    	# x: 거슬러줘야하는 금액
        for x in range(n+1):
            # 거슬러줘야하는 금액을 지불가능한 동전보다 클 경우
            if x >= money[y]:
                dp[y][x] = (dp[y-1][x] + dp[y][x - money[y]]) % 1000000007
            # 반대의 경우
            else:
                dp[y][x] = dp[y-1][x]
    
    # 마지막 값 출력
    return dp[-1][-1]

dp를 행렬 기준으로 바라볼때

행은 현재 가지고 있는 동전을 의미하고 열은 지불하고자 하는 금액을 의미하게된다.

첫번째 행은 첫번째 동전은 1원이고 0~5원 모두 표현이 1원으로 가능하기때문에 1을 넣어준다.

만약 첫번째 동전이 2원이라 했다면 0원, 2원, 4원에만 1로 표시가 될것이다.

 

이후 지불가능할 동전이 2원이라 가정하고 지불해야할 금액을 4원이라고 한다면 

4 >= 2이기 때문에 즉 지불이 가능하기 때문에

이전행 1원으로 4원을 표현가능한 숫자에서 해당 2원으로 2원(4원-2원) 지불이 가능한 값을 더해주는 것이다.

즉 4원을 표시할때는 1원x4개 + 2원x2개 총 2가지의 경우의 수로 표현이 가능하다는 뜻이다.

 

dp기초 문제인것같은데 문제에 대해서 고민을 많이했습니다... 아직 dp에 대해서 미숙한점이 많아서 많은 문제를 풀고 공부를 해야겠다는 생각이 많이 들었습니다.


  • 출처

programmers.co.kr/learn/courses/30/lessons/12907?language=python3

728x90

댓글