섹션 10 Dynamic Programming - 5. 동전교환(냅색 알고리즘)

설명

여러 종류의 동전이 주어졌을 때, 어떤 금액 M을 가장 적은 수의 동전으로 교환하는 문제입니다.
단, 각 동전은 무한히 사용할 수 있습니다.

이 문제는 냅색 알고리즘(Unbounded Knapsack, 무한대 개수의 아이템을 사용하는 DP)의 대표 문제입니다.

 

냅색(배낭) 알고리즘 :  주어진 제한(무게, 금액 등) 안에서 최대 가치나 최적의 결과를 찾는 DP 알고리즘입니다.

---

입력

• 첫 번째 줄: 동전의 종류 개수 N (1 ≤ N ≤ 50)
• 두 번째 줄: N개의 동전 단위 (각 단위는 100원 이하 자연수)
• 세 번째 줄: 거슬러줄 금액 M (1 ≤ M ≤ 500)

---

출력

• 금액 M을 거슬러줄 때 사용되는 최소 동전 개수

---

예시

# 예시 입력
3
1 2 5
15

# 예시 출력
3

설명

5 + 5 + 5 = 15
→ 동전 3개로 해결할 수 있으므로 최소 개수는 3

---

코드 구현

import java.util.*;

public class Main {
	static int n, m;
	static int[] dy;

	public int solution(int[] coin) {
		Arrays.fill(dy, Integer.MAX_VALUE);
		dy[0] = 0;

		for (int i = 0; i < n; i++) {
			for (int j = coin[i]; j <= m; j++) {
				if (dy[j - coin[i]] != Integer.MAX_VALUE) {
					dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1);
				}
			}
		}
		return dy[m];
	}

	public static void main(String[] args) {
		Main T = new Main();
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		int[] arr = new int[n];
		for (int i = 0; i < n; i++) {
			arr[i] = sc.nextInt();
		}
		m = sc.nextInt();
		dy = new int[m + 1];
		System.out.print(T.solution(arr));
		sc.close();
	}
}

---

코드 설명 (DP + 냅색 알고리즘)

• dy[j]: 금액 j를 만들기 위한 최소 동전 개수
• dy[0] = 0: 금액 0을 만들기 위한 동전 개수는 0
• 나머지는 Integer.MAX_VALUE로 초기화하여 불가능한 상태로 시작

DP 점화식

dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1)

• coin[i]를 사용하여 금액 j를 만들 수 있는 경우
• j - coin[i]를 만들 수 있었다면, 거기에서 하나 더해 j를 만들 수 있음

---

시간 복잡도 분석

• O(N * M)
  • N: 동전 종류 수 (최대 50)
  • M: 목표 금액 (최대 500)
  • 이중 반복문 구조로 25,000번 연산 → 매우 빠르게 처리 가능

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런