[100일의 IT 초보 탈출] #64 동전 교환 문제 _ 정해진 금액을 만들 수 있는 방법은?

@Prof.SSong·2025. 7. 3. 22:59

728x90

오늘은 무엇을 배우게 될까요?

“500원, 100원, 50원이 있을 때 1000원을 만드는 방법은 몇 가지일까?”

이런 문제는 단순한 수학이 아니라, 조합과 최적화가 섞인 컴퓨터 알고리즘 문제입니다.

동전 교환 문제는

“정해진 동전 종류로 목표 금액을 만들기 위한 방법의 수 또는 최소 동전 수”를 구하는 문제입니다.

이 문제는 무한 배낭 문제의 대표적 사례입니다.

문제 유형 분류

동전 교환 문제는 크게 2가지 버전으로 나뉩니다

유형 설명 목표

방법 수 구하기	동전을 조합해 금액을 만들 수 있는 경우의 수	총 몇 가지 방법?
최소 개수 구하기	해당 금액을 만들 수 있는 최소 동전 수	가장 효율적인 조합?

유형 ①: 방법 수 구하기 (DP 방식)

문제 예시

동전 종류: [1, 2, 5]
목표 금액: 5
가능한 조합:
- 1+1+1+1+1
- 1+1+1+2
- 1+2+2
- 5
- …
결과: 4가지 방법

점화식 설계 (방법 수)

dp[i]: i원을 만드는 방법의 수
dp[0] = 1 (0원을 만드는 방법은 아무 동전도 쓰지 않는 1가지)

def count_ways(coins, target):
    dp = [0] * (target + 1)
    dp[0] = 1
    
    for coin in coins:
        for i in range(coin, target + 1):
            dp[i] += dp[i - coin]
    
    return dp[target]

print(count_ways([1, 2, 5], 5))  # 출력: 4

유형 ②: 최소 개수 구하기

이번엔 경우의 수가 아니라,

동전 개수를 최소로 써서 목표 금액을 만드는 게 목표입니다.

동전 종류: [1, 3, 4]
목표 금액: 6
최소 동전 수
- 3 + 3 = 2개
- 4 + 1 + 1 = 3개 → ❌
- 답: 2개

점화식 설계 (최소 개수)

dp[i]: i원을 만드는 최소 동전 개수
dp[0] = 0, 나머지는 inf로 초기화
점화식: dp[i] = min(dp[i], dp[i - coin] + 1)

def min_coins(coins, target):
    dp = [float('inf')] * (target + 1)
    dp[0] = 0

    for coin in coins:
        for i in range(coin, target + 1):
            dp[i] = min(dp[i], dp[i - coin] + 1)

    return dp[target] if dp[target] != float('inf') else -1

print(min_coins([1, 3, 4], 6))  # 출력: 2

시각적으로 요약해보자면

금액(i) 최소 동전 수 (coins=[1,3,4])

0	0
1	1 (1)
2	2 (1+1)
3	1 (3)
4	1 (4)
5	2 (1+4 or 1+1+3)
6	2 (3+3)

실제 활용 예시

활용 상황설명

거스름돈 계산	최소 동전 개수로 거슬러 주기
포인트 시스템	적은 자원으로 보상 구성
구매 조합	예산 내 다양한 조합 구하기
AI 게임 설계	자원 최소 소비 루트 찾기

한 줄 요약

👉 동전 교환 문제는 목표 금액을 만들기 위한 방법의 수 또는 최소 동전 수를 구하는 문제로,

무한 배낭 문제의 대표적인 실전 사례입니다.