프로그래머스 | Python | DP:테뷸레이션 | 거스름돈 (Lv.3)

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

프로그래머스

 

이 문제는 동전으로 특정 금액을 만드는 방법의 수를 구하는 문제이며, 동적 계획법(Dynamic Programming, DP)을 사용하여 해결할 수 있습니다.

---

📌 문제 분석

• n: 거슬러 줘야 할 총 금액.
• money: 사용할 수 있는 동전의 종류 리스트.
• 목표: n원을 만들 수 있는 방법의 수를 찾는 것.
• 단, 정답이 커질 수 있으므로 1,000,000,007로 나눈 나머지를 반환해야 합니다.

---

📌 핵심 알고리즘 - 동적 계획법(DP:테뷸레이션(Bottom-Up DP))

이 문제는 "거스름돈 문제(Coin Change Problem)"와 매우 유사합니다.

여러 개의 동전으로 특정 금액을 만드는 경우의 수를 구할 때는 배낭 문제(Knapsack Problem)에서 쓰이는 DP 기법을 활용하면 효과적입니다.

---

📌 접근 방법

1️⃣ DP 배열 정의 (어떤 값을 저장할까?)

• dp[i]는 i원을 만들 수 있는 방법의 수를 저장하는 배열입니다.
• dp[0] = 1 → 아무 동전도 사용하지 않고 0원을 만드는 방법은 1가지(=아무것도 안 함).
• 처음에는 dp[1]부터 dp[n]까지 0으로 초기화 (아직 방법을 찾지 않았으므로).
• dp 배열의 크기가 n+1인 이유는, 0원부터 n원까지의 모든 경우를 저장해야 하기 때문입니다.

---

2️⃣ DP 점화식 (어떻게 계산할까?)

동전을 하나씩 추가하면서, 만들 수 있는 금액을 업데이트합니다.

점화식: dp[i]=dp[i]+dp[i−coin] 

dp[i] = dp[i] + dp[i - coin]의 의미

✅ 기존에 i원을 만드는 방법이 있다면,

✅ "새로운 동전(coin)을 사용하면 i - coin원을 만들던 방법을 활용할 수 있다!"

예를 통해 더 자세히 알아봅시다.

예제 1️⃣: dp[5]를 구할 때, coin = 2

✔ 우리가 5원을 만들려고 할 때, "2원을 새롭게 추가해서 5원을 만들 수 있는 경우"를 생각해봅시다.

⇒ "5원짜리 방법을 직접 세는 것이 아니라, 기존에 3원을 만들던 방법에서 2원을 추가하면 된다!"

기존 경우 (dp[5])

• dp[5]에는 이미 이전 동전(1원)만 사용해서 만든 경우가 저장되어 있음.
  •   예: 1+1+1+1+1

새로운 경우 (dp[i - coin] → dp[3]을 이용)

• 3원(dp[3])을 만드는 방법이 있으면, 거기에 2원을 추가해서 5원을 만들 수 있음!
  •   예: 1+1+1 (dp[3]) + 2 → (2+1+1+1)
  •   예: 2+1 (dp[3]) + 2 → (2+2+1)

한마디로, dp[5]를 만들 때 dp[3]을 참고하는 이유는?

✔ dp[3]까지는 이미 구해둔 경우의 수가 있음.

✔ 여기서 새로운 동전(2원)을 사용하면, 3 + 2 = 5원을 만들 수 있는 새로운 방법이 추가됨!

진짜 쉽게 말하자면!

"기존에 만들던 방법(dp[i])을 유지하면서, 새로운 동전이 들어올 때 기존 금액(dp[i - coin])을 활용해서 새로운 방법을 더하는 것!"

쉽게 이해하는 공식!

💡 "dp[i]는 기존 방법 + dp[i - coin]을 이용한 새로운 방법!"

---

3️⃣ MOD 연산 적용 (너무 커지면 숫자를 줄이자!)

• 경우의 수가 엄청 커질 수 있기 때문에, 숫자가 너무 커지는 걸 방지해야 합니다.
• 그래서 1,000,000,007로 나눈 나머지를 저장합니다.

MOD 연산 적용: dp[i]=(dp[i]+dp[i−coin])mod1,000,000,007 

이게 무슨 의미일까요?

• 매번 계산할 때 MOD를 적용해서 값이 너무 커지는 걸 방지하는 것입니다.
• 예를 들어, dp[100000]을 구할 때 값이 10억 이상 될 수도 있는데, 그럼 컴퓨터가 처리하기 힘들어집니다.
• 그래서 항상 1,000,000,007로 나눈 나머지만 저장합니다.

---

📌 코드 구현

def solution(n, money):
    MOD = 1_000_000_007  # 오버플로우 방지를 위한 MOD 연산
    dp = [0] * (n + 1)
    dp[0] = 1  # 0원을 만드는 방법은 1 (아무 동전도 사용하지 않음)

    for coin in money:  # 각 동전에 대해
        for i in range(coin, n + 1):  # 해당 동전으로 만들 수 있는 금액부터 갱신
            dp[i] = (dp[i] + dp[i - coin]) % MOD  # MOD 연산 적용

    return dp[n]  # n원을 만드는 방법의 수 반환

---

📌 예제 실행

💡 print(solution(5, [1, 2, 5])) 실행 과정

✅ 문제 요약:

동전 [1, 2, 5]를 사용해서 5원을 만드는 방법의 개수를 구하는 문제입니다.

DP 테이블(dp[i])을 이용해서 각 금액을 만드는 경우의 수를 저장하면서 해결합니다.

---

📌 1️⃣ solution(5, [1, 2, 5]) 실행 과정

1. dp 배열 초기화

우선, dp 배열을 초기화합니다.

dp = [1, 0, 0, 0, 0, 0]

✔ dp[0] = 1인 이유: 0원을 만드는 방법은 아무 동전도 사용하지 않는 1가지 방법뿐이므로 1입니다.

✔ dp[1] ~ dp[5] = 0: 아직 방법을 찾지 않았으므로 0.

---

2️⃣ 동전 1원 사용 (coin = 1)

• 1원을 이용해서 dp 배열을 업데이트합니다.
• for i in range(1, 6): → 1원으로 1~5원을 만들 수 있는 방법을 업데이트.

dp[1] = dp[1] + dp[0]  # 1원을 만들 수 있는 방법: 1가지 (1)
dp[2] = dp[2] + dp[1]  # 2원을 만들 수 있는 방법: 1가지 (1+1)
dp[3] = dp[3] + dp[2]  # 3원을 만들 수 있는 방법: 1가지 (1+1+1)
dp[4] = dp[4] + dp[3]  # 4원을 만들 수 있는 방법: 1가지 (1+1+1+1)
dp[5] = dp[5] + dp[4]  # 5원을 만들 수 있는 방법: 1가지 (1+1+1+1+1)

🔹 1원 사용 후 dp 배열

dp = [1, 1, 1, 1, 1, 1]

✔ 1원만 사용해서는 각 금액을 만드는 방법이 오직 1가지뿐입니다.

---

3️⃣ 동전 2원 사용 (coin = 2)

• 2원을 추가하여 dp 배열을 업데이트합니다.
• for i in range(2, 6): → 2원으로 2~5원을 만들 수 있는 방법을 업데이트.

dp[2] = dp[2] + dp[0]  # 2원을 만들 수 있는 새로운 방법 추가 (2)
dp[3] = dp[3] + dp[1]  # 3원을 만들 수 있는 새로운 방법 추가 (2+1)
dp[4] = dp[4] + dp[2]  # 4원을 만들 수 있는 새로운 방법 추가 (2+2, 2+1+1)
dp[5] = dp[5] + dp[3]  # 5원을 만들 수 있는 새로운 방법 추가 (2+2+1, 2+1+1+1)

🔹 2원 사용 후 dp 배열

dp = [1, 1, 2, 2, 3, 3]

✔ 2원이 추가되면서 새로운 방법이 추가됨!

✔ 예를 들어, 4원을 만드는 방법이 2+2로 늘어났음.

---

4️⃣ 동전 5원 사용 (coin = 5)

• 5원을 추가하여 dp 배열을 업데이트합니다.
• for i in range(5, 6): → 5원으로 5원을 만들 수 있는 방법을 업데이트.

dp[5] = dp[5] + dp[0]  # 5원을 만들 수 있는 새로운 방법 추가 (5)

🔹 5원 사용 후 dp 배열

dp = [1, 1, 2, 2, 3, 4]

✔ 5원이 추가되면서 5원을 만드는 새로운 방법(5 단독)이 추가됨!

✔ 최종적으로 dp[5] = 4 → 5원을 만드는 방법은 총 4가지!

---

📌 5️⃣ 최종 결과

🔹 dp[5] = 4 → 5원을 만드는 방법의 개수는 4가지

 

금액	가능한 방법
5	5
2 + 2 + 1	2
2 + 1 + 1 + 1	3
1 + 1 + 1 + 1 + 1	4

---

📌 최종 코드 실행 과정 정리

동전 1 사용 후: [1, 1, 1, 1, 1, 1]
동전 2 사용 후: [1, 1, 2, 2, 3, 3]
동전 5 사용 후: [1, 1, 2, 2, 3, 4]  (최종 결과)

✔ print(solution(5, [1, 2, 5])) 출력 값은 4

✔ 즉, 5원을 만드는 방법은 총 4가지!

---

📌 dp[i] = dp[i] + dp[i - coin] 의미 다시 정리

dp[i]는 원래의 경우의 수 + 새로운 동전을 추가했을 때 경우의 수!

즉, dp[i - coin]의 값을 dp[i]에 더하는 것은 "새로운 동전으로 만들 수 있는 경우의 수를 누적"하는 것!

---

📌 핵심 개념 요약

 

핵심 개념	설명
동적 계획법 (DP)	특정 금액을 만드는 방법의 수를 저장하여 중복 계산을 줄임
점화식	dp[i] = dp[i] + dp[i - coin]
MOD 연산 적용	1,000,000,007로 나머지 연산을 수행하여 오버플로우 방지
배낭 문제 (Knapsack Problem)	물건을 넣을 때 최적의 조합을 찾는 문제와 유사

---

📌 출제 의도

1. 동적 계획법(DP)의 개념을 이해하고 적용할 수 있는가?
2. 배낭 문제(Knapsack Problem) 유형의 변형을 해결할 수 있는가?
3. MOD 연산을 활용하여 큰 수 처리를 할 수 있는가?

---

📌 시간 복잡도 분석

• 이중 반복문 실행: O(n * m)
  •   n: 거슬러 줄 총 금액
  •   m: 동전 개수
• n이 최대 100,000이고, 동전 개수 m이 최대 100개여서, 최대 10^7번 연산으로 해결 가능.→ 충분히 빠름 (효율적).

---