사용자 도구

사이트 도구


ps:problems:programmers:12907

거스름돈

ps
링크programmers.co.kr/…
출처프로그래머스
문제 번호12907
문제명거스름돈
레벨Level 3
분류

DP

시간복잡도O(nm)
인풋사이즈n<=10^5, m<=10^2
사용한 언어Python
해결날짜2020/11/16
  • 많은 교과서의 2차원 DP 챕터에서 연습문제로 자주 보이는 유명한 문제이다.

풀이

  • dp[m][n]을 money[0]부터 money[m]까지의 화폐를 가지고 n원을 만들 수 있는 방법의 수라고 하자.
  • 이 것을, money[m] 없이 n원을 만드는 방법과 money[m]을 포함해서 만드는 방법으로 나누어 생각하자
    • money[m]없이 n원을 만드는 방법은 dp[m-1][n]과 같다
    • money[m]을 한번 이상 포함해서 n원을 만드는 방법은, 어떤식으로 n-money[m] 원을 만들고 마지막으로 money[m]짜리 화폐를 한번 사용한다고 생각하면 된다. 즉, dp[m][n-money[m]]이다
  • 종합하면 dp[m][n] = dp[m-1][n] + dp[m][n-money[m]] 이고, O(NM)에 풀리게 된다.
  • 공간복잡도 측면에서는 N*M 테이블을 전부 만들 필요가 없다. dp[m][…] 를 계산하기 위해서는 dp[m-1][…] 만 필요하고 dp[m-2]..이하의 행은 필요가 없다. 따라서 두개의 행만 유지하면 된다. 따라서 공간복잡도는 O(NM)이 아니라 O(N)이다.
    • 그리고, 실제로 이 문제에서는 두 개의 행도 필요 없고, 하나의 행만 유지하면서 갱신해나갈수 있다.

코드

"""Solution code for "Programmers 12907. 거스름돈".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/12907
- Solution link: http://www.teferi.net/ps/problems/programmers/12907
"""

MOD = 1_000_000_007


def solution(n, money):
    dp = [1] + [0] * n
    for cur_money in money:
        for i in range(cur_money, n + 1):
            dp[i] = (dp[i] + dp[i - cur_money]) % MOD

    return dp[n]

토론

댓글을 입력하세요:
E​ U F H Y
 
ps/problems/programmers/12907.txt · 마지막으로 수정됨: 2021/01/25 14:05 저자 teferi