백준 14916번 - 거스름돈

거스름돈 문제 바로 가기

풀이 날짜: 2026-01-13

baekjoon 알고리즘 문제 풀이

풀이 코드

import sys
input = sys.stdin.readline

n = int(input())
INF = 100000
dp = [INF] * (n+1)
dp[0] = 0

for i in range(1,n+1):
    if i>=2:
        dp[i] = min(dp[i], dp[i-2]+1)
    if i>=5:
        dp[i] = min(dp[i], dp[i-5]+1)
if dp[n] == INF:
    print(-1)
else:
    print(dp[n])
  

문제 접근

이 문제는 2원과 5원 동전만을 사용해 주어진 금액을 만들 때 필요한 최소 동전 개수를 구하는 문제다. 처음에는 5원을 최대한 쓰는 방식의 그리디로 접근할 수 있을 것처럼 보이지만, 일부 금액(예: 13원)에서는 단순한 직관이 쉽게 깨진다. 따라서 이 문제는 “이 금액을 만들 수 있는 최소 개수”를 누적해서 계산하는 동적 계획법(DP) 으로 접근하는 것이 가장 안전하다.

DP 정의

• dp[i] = i원을 만들기 위해 필요한 최소 동전 개수

헷갈렸던 점 정리

초기값 설정의 중요성

처음에는 dp = [0] * (n+1) 처럼 초기화하려고 했지만, 이는 모든 금액을 0개의 동전으로 만들 수 있다고 착각하게 만드는 위험한 초기화다. 따라서 만들 수 없는 상태를 명확히 구분하기 위해 다음과 같이 설정했다.

• dp[0] = 0 → 0원은 동전 0개
• 나머지는 모두 INF → 아직 만들 수 없음을 의미