[프로그래머스/Lv. 3] - 거스름돈

문제 링크

코드

실패

#  거슬러 줄 방법의 수 구하기.
MOD = 1000000007
def solution(n, money):
    answer = 0
    dp = [0] * (n + 1)
    dp[0] = 1
    
    # 실패 코드 - 거스름돈을 먼저 설정하기
    for i in range(1, n + 1):
        for m in money:
            dp[i] += dp[i - m] % MOD
    
    return dp[n]

얼마를 거슬러줄 것인지, 거스름돈을 먼저 설정한 로직이다.
n=5, money=[1,2,5] 일 때를 살펴보자.

• i = 1 ➡️ dp[1] += dp[1 - 1] = dp[0] = 1
• i = 2 ➡️ dp[2] += (dp[2 - 1] = dp[1] = 1) + (dp[2 - 2] = dp[0] = 1) = 2
• i = 3 ➡️ dp[3] += (dp[3 - 1] = dp[2] = 2) + (dp[3 - 2] = dp[1] = 1) = 3
• i = 4 ➡️ dp[4] += (dp[4 - 1] = dp[3] = 3) + (dp[4 - 2] = dp[2] = 2) = 5
• i = 5 ➡️ dp[5] += (dp[5 - 1] = dp[4] = 5) + (dp[5 - 2] = dp[3] = 3) + (dp[5 - 5] = dp[0] = 1) = 9

dp[5] = 9 임을 보아, 로직이 제대로 틀렸다.

왜 거스름돈을 먼저 설정하면 틀리는걸까?

경우의 수를 만드는 과정을 다시 살펴보자.
i = 1일 때..

// 1원 하나로 만드는 경우의 수
1 

i = 2일 때..

// += dp[1] => 즉, 1원을 만드는 경우의 수에 1원을 추가한 것
1 + 1
// 2원 하나로 만드는 경우의 수
2

i = 3일 때..

// += dp[2] => 즉, 2원을 만드는 경우의 수에 1원을 추가한 것
2 + 1
1 + 1 + 1
// += dp[1] => 즉, 1원을 만드는 경우의 수에 2원을 추가한 것
1 + 2

i = 4일 때..

// += dp[3] => 즉, 3원을 만드는 경우의 수에 1원을 추가한 것
2 + 1 + 1
1 + 1 + 1 + 1
1 + 2 + 1
// += dp[2] => 즉, 2원을 만드는 경우의 수에 2원을 추가한 것
1 + 1 + 2
2 + 2

i = 5일 때..

// += dp[4] => 즉, 4원을 만드는 경우의 수에 1원을 추가한 것
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
1 + 2 + 1 + 1
// += dp[3] => 즉, 3원을 만드는 경우의 수에 2원을 추가한 것
2 + 1 + 2
1 + 1 + 1 + 2
1 + 2 + 2
// += dp[0] => 즉, 5원 하나로 만드는 경우의 수
5

3원을 만드는 경우의 수에서 1 + 2 는 2 + 1과 같다.
즉, 여기서는 중복되는 경우의 수도 다른 것이라고 판단하고 경우의 수에 추가한다.

---

성공

#  거슬러 줄 방법의 수 구하기.
MOD = 1000000007
def solution(n, money):
    answer = 0
    dp = [0] * (n + 1)
    dp[0] = 1
    
    # 성공 코드 - 동전의 종류 먼저 설정하기
    for m in money:
        for i in range(m, n + 1):
            dp[i] += dp[i - m] % MOD
    
    return dp[n]

중복을 피하기 위해서는, 동전의 종류를 먼저 설정하면 된다.