섹션 8 DFS, BFS - 5. 동전교환

📌 문제 설명

여러 단위의 동전이 주어졌을 때
무한히 동전을 사용 가능하다면
주어진 금액 M을 최소 개수의 동전으로 교환하는 방법은 무엇일까?

---

📝 입력 & 출력

입력

• 첫 줄: 동전 종류 수 N (1 ≤ N ≤ 12)
• 둘째 줄: N개의 동전 단위 (각각 100원을 넘지 않음)
• 셋째 줄: 거슬러 줄 금액 M (1 ≤ M ≤ 500)

출력

• 거슬러 줄 수 있는 최소 동전 개수

---

🔹 예제 입력 & 출력

예제 입력

 

3
1 2 5
15

예제 출력

 

3

💬 설명

• 5원짜리 3개로 15원을 만들 수 있음 → 동전 3개

---

💡 해결 방법

✅ 핵심 전략: DFS + 백트래킹

• 가능한 모든 동전 조합을 시도하면서 최소 개수인 경우만 추적
• 중복 사용 가능 → 동전 하나를 여러 번 선택 가능
• 백트래킹 조건:
  • 현재 사용한 동전 수(L)가 answer 이상이면 중단
  • 현재 합(sum)이 M을 초과하면 중단

---

✅ 동전 정렬 이유

• 큰 동전부터 먼저 시도하면 빠르게 최적해를 찾을 가능성↑
• Arrays.sort(coin, Collections.reverseOrder()) 사용

---

💻 코드 구현 (Java)

package partDfsBfs;

import java.util.*;

public class Problem5 {
	static int n, m, answer = Integer.MAX_VALUE;

	public void DFS(int L, int sum, Integer[] coin) {
		if (sum > m) return;              // 가지치기 ①: 합이 초과
		if (L >= answer) return;          // 가지치기 ②: 더 많은 동전 사용
		if (sum == m) {
			answer = Math.min(answer, L); // 최솟값 갱신
		} else {
			for (int i = 0; i < n; i++) {
				DFS(L + 1, sum + coin[i], coin);
			}
		}
	}

	public static void main(String[] args) {
		Problem5 T = new Problem5();
		Scanner kb = new Scanner(System.in);
		n = kb.nextInt();
		Integer[] coin = new Integer[n];
		for (int i = 0; i < n; i++) coin[i] = kb.nextInt();
		Arrays.sort(coin, Collections.reverseOrder()); // 큰 동전부터
		m = kb.nextInt();
		T.DFS(0, 0, coin);
		System.out.println(answer);
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 입력 및 정렬

Arrays.sort(coin, Collections.reverseOrder());

• 큰 동전부터 먼저 탐색하여 빠르게 최적해 도달

---

2️⃣ DFS 함수

DFS(L + 1, sum + coin[i], coin);

• 각 동전을 중복 허용하여 계속 시도
• L: 현재 사용한 동전 수
• sum: 현재까지의 누적 금액

---

3️⃣ 가지치기

if (sum > m) return;
if (L >= answer) return;

• 시간 단축을 위한 필수 조건
• answer는 현재까지 찾은 최소 동전 수

---

⏳ 시간 복잡도 분석

• 최대 깊이: M (1원짜리로만 만드는 경우)
• 각 단계마다 N개의 동전 선택
• 최악의 경우: O(N^M)
• 하지만 가지치기 덕분에 실질 탐색 수는 매우 줄어듦

 

---

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

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

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