알고리즘

[프로그래머스] 12907 거스름돈

2025년 12월 18일
37
#Python 3#알고리즘#프로그래머스

[level 3] 거스름돈 - 12907

문제 링크

성능 요약

메모리: 12.1 MB, 시간: 639.44 ms

구분

코딩테스트 연습 > 연습문제

채점결과

정확성: 70.0
효율성: 30.0
합계: 100.0 / 100.0

문제 설명

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 해주세요.
입출력 예
nmoneyresult
5[1,2,5]4
입출력 예 설명

입출력 예 #1

문제의 예시와 같습니다.

출처: 프로그래머스 코딩 테스트 연습, https://school.programmers.co.kr/learn/challenges

문제 풀이

문제 분석

이 문제는 주어진 금액 n을 특정 화폐 단위 money들로 거슬러 줄 수 있는 방법의 총 가지 수를 계산하는 문제입니다. 각 화폐 단위는 무한하게 사용할 수 있으며, 거스름돈을 만드는 순서는 중요하지 않고 최종 조합의 개수만 중요합니다. 예를 들어 1원, 2원으로 3원을 만드는 경우 (1+1+1), (1+2) 두 가지 방법이 있습니다. 정답이 매우 커질 수 있으므로, 결과를 1,000,000,007로 나눈 나머지를 반환해야 합니다.

  • 입력:
    • n: 거슬러 줘야 하는 총 금액 (100,000 이하의 자연수)
    • money: 사용할 수 있는 화폐 단위들을 담은 리스트 (100종류 이하)
  • 출력: n원을 거슬러 줄 수 있는 방법의 수 (1,000,000,007로 나눈 나머지)

접근 방법

이 문제는 전형적인 동적 계획법(Dynamic Programming, DP) 문제 중 하나인 "거스름돈 조합의 수" 문제입니다. 특정 금액 i를 만들 수 있는 방법의 수를 dp[i]에 저장하고, 작은 금액부터 점진적으로 계산하여 목표 금액 n까지 도달하는 방식으로 해결할 수 있습니다.

핵심 아이디어는 다음과 같습니다: dp[i] = 금액 i를 만들 수 있는 방법의 수 새로운 화폐 단위 coin을 고려할 때, coin을 사용하여 금액 amount를 만드는 방법은, coin을 사용하지 않고 amount를 만드는 방법의 수와 coin을 한 번 사용하고 남은 금액 amount - coin을 만드는 방법의 수를 더하는 것과 같습니다. 이 때, coin을 사용하지 않고 amount를 만드는 방법의 수는 이미 이전 화폐 단위들로 계산된 dp[amount] 값이며, coin을 한 번 사용하고 amount - coin을 만드는 방법의 수는 dp[amount - coin] 입니다.

주의할 점은, 화폐 단위 money 리스트를 순회하면서 각 화폐 단위를 가지고 만들 수 있는 금액을 갱신해야 한다는 것입니다. 이렇게 해야 (1원 1개, 2원 1개)와 (2원 1개, 1원 1개)를 같은 방법으로 취급하여 조합의 수를 올바르게 셀 수 있습니다. 만약 금액을 먼저 순회하고 화폐 단위를 나중에 순회하면 순서가 다른 경우를 다른 방법으로 세어버려 순열의 수가 됩니다.

구현 설명

1단계: DP 테이블 초기화

  • dp = [0] * (n+1): dp 배열을 생성하고 모든 값을 0으로 초기화합니다. dp[i]는 i원을 만들 수 있는 방법의 수를 저장할 것입니다. 배열의 크기는 n+1로, 0원부터 n원까지의 경우를 모두 커버합니다.
  • dp[0] = 1: 0원을 만드는 방법은 "아무것도 사용하지 않는 것" 한 가지이므로, dp[0]를 1로 초기화합니다. 이는 다른 금액을 계산할 때 기준점 역할을 합니다. 예를 들어, 1원짜리 동전으로 1원을 만들 때, dp[1] += dp[1-1] 즉 dp[1] += dp[0]이 되는데, dp[0]이 1이므로 1원을 만드는 한 가지 방법이 올바르게 카운트됩니다.

2단계: 각 화폐 단위에 대해 반복

  • for coin in money:: money 리스트에 있는 각 화폐 단위(coin)에 대해 반복문을 실행합니다. 이 외부 반복문이 중요합니다. 각 화폐 단위를 한 번씩 "새롭게" 고려하여, 이 화폐 단위를 사용하여 만들 수 있는 모든 금액의 경우의 수를 갱신합니다.

3단계: 현재 화폐 단위로 만들 수 있는 금액 갱신

  • for amount in range(coin, n+1):: 현재 고려 중인 화폐 단위 coin을 사용하여 만들 수 있는 모든 금액 amount에 대해 내부 반복문을 실행합니다. amount는 최소한 coin 값 이상이어야 해당 coin을 사용할 수 있으므로 coin부터 n까지 반복합니다.
  • dp[amount] += dp[amount - coin]: 현재 amount를 만들 수 있는 방법의 수에 dp[amount - coin] 값을 더합니다. 이 의미는 amount를 만드는 방법 중, 현재 coin을 한 개 사용하는 경우(amount - coin을 만든 후 coin을 하나 추가)를 기존 경우의 수에 더하는 것입니다.
    • 예를 들어, dp[3]을 계산하는데 coin=2일 경우, dp[3]에는 dp[3-2] 즉 dp[1]이 더해집니다. 이는 1원을 만든 후 2원짜리 동전을 추가하여 3원을 만드는 경우의 수를 의미합니다.
  • dp[amount] %= 1000000007: 계산된 dp[amount] 값이 정수 오버플로우를 방지하고 문제의 요구사항을 충족시키기 위해 1,000,000,007로 나눈 나머지로 저장됩니다.

4단계: 최종 결과 반환

  • return dp[n]: 모든 화폐 단위에 대해 n원까지의 모든 경우의 수를 계산한 후, dp[n]에 저장된 최종 값을 반환합니다. 이 값이 n원을 거슬러 줄 수 있는 총 방법의 수가 됩니다.

⏱복잡도 분석

  • 시간 복잡도: O(M * N)

    • 외부 반복문: money 리스트의 길이 M (화폐 단위의 개수)만큼 반복합니다. (M은 최대 100)
    • 내부 반복문: n까지의 amount에 대해 반복합니다. 최악의 경우 약 N번 반복합니다. (N은 최대 100,000)
    • 내부 연산: 각 dp 업데이트는 상수 시간에 이루어집니다.
    • 따라서 총 시간 복잡도는 M * N에 비례합니다. (100 * 100,000 = 10,000,000 연산) 이는 일반적인 시간 제한(1초에 1억 연산) 내에 충분히 해결 가능한 수준입니다.

  • 공간 복잡도: O(N)

    • dp 배열은 n+1 크기로 생성됩니다.
    • 따라서 공간 복잡도는 N에 비례합니다. (N은 최대 100,000) 이는 약 400KB ~ 800KB 정도의 메모리를 사용하므로, 일반적인 메모리 제한(256MB 이상) 내에 충분히 가능합니다.

핵심 포인트

  1. 동적 계획법 (Dynamic Programming): 작은 문제(특정 금액 i를 만드는 방법)의 해를 기반으로 큰 문제(특정 금액 n을 만드는 방법)의 해를 효율적으로 계산합니다.
  2. dp[0] = 1 초기화: 0원을 만드는 방법이 1가지(아무것도 사용하지 않음)라는 베이스 케이스 설정은 다른 금액을 계산할 때 기준점이 되어 올바른 경우의 수를 계산하는 데 필수적입니다.
  3. 반복문 순서 (for coin, then for amount): 화폐 단위를 먼저 순회하고, 그 화폐 단위를 사용하여 만들 수 있는 금액들을 갱신하는 방식으로 문제를 해결해야 합니다. 이렇게 해야 "조합"의 수를 올바르게 셀 수 있습니다. 만약 금액을 먼저 순회하고 그 금액을 만들 수 있는 동전을 나중에 순회하면 순서가 다른 경우를 다르게 세어 "순열"의 수가 됩니다.
  4. 모듈러 연산: 결과 값이 매우 커질 수 있으므로, 각 dp 값을 갱신할 때마다 1,000,000,007로 나눈 나머지를 저장하여 오버플로우를 방지하고 문제 요구사항을 충족시킵니다.

풀이 코드

def solution(n, money):
    dp = [0] * (n+1)
    dp[0] = 1

    for coin in money:
        for amount in range(coin, n+1):
            dp[amount] += dp[amount - coin]
            dp[amount] %= 1000000007

    return dp[n]
댓글을 불러오는 중...