[백준 #11047] 동전 0

https://www.acmicpc.net/problem/11047

 

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.
동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)
둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ A_i ≤ 1,000,000, A_1 = 1, i ≥ 2인 경우에 A_i는 A_i-1의 배수)

 

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

예제 입력 1

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력 1

6

 

예제 입력 2

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

 

예제 출력 2

12

 

해결 코드

import java.util.Scanner;

public class Main {
	
	public static void main(String args[]) {
		// N개의 종류 동전, 무제한 개
		// 최소 동전 개수 구하기 -> greedy
		// 각 동전들은 모두 배수관계. 즉 큰 수부터 들어가면 greedy에서 아무 문제가 없다.
		
		Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int k = scanner.nextInt();
		
		int[] coins = new int[n];
		for(int i=0; i<n; i++) coins[i] = scanner.nextInt();
		
		int ans = 0;
		int idx = n-1;
		
		while(idx >= 0) {
			int coin = coins[idx];
			
			if(coin > k) { // 만들려는 수보다 코인이 더 큰 수면 그 다음 작은 코인으로 넘어가야 함.
				idx--;
				continue;
			}
			
			else {
				ans += k / coin;
				k %= coin;
				idx--;
			}
			
		}
		
		System.out.print(ans);
		
	}

}

 

 

 

---

 

위 문제를 해결하기 위해서는 그리디 알고리즘(Greedy Algorithm)을 이용해 주어진 금액을 최소 개수의 동전으로 만들기 위한 프로그램을 짜면 된다. 배수 관계에 있는 동전들이므로 그리디 전략이 유효하며, 가장 큰 가치의 동전부터 사용하기만 해도 최적의 해를 보장할 수 있다.

 

1. 주요 개념

(1) 그리디 알고리즘 (Greedy Algorithm)

• 정의: 매 단계에서 가장 최선이라고 생각되는 선택을 하는 방법.

• 적용 이유:

• 문제에서 각 동전이 배수 관계에 있다.

• 예를 들어, 동전 종류가 1, 5, 10, 50, 100, 500이라면 큰 동전이 항상 작은 동전의 배수다.

• 이런 경우 큰 동전부터 사용하면 항상 최소 개수의 동전을 사용할 수 있다.

• 따라서, 큰 가치의 동전부터 차례로 선택해 나가는 전략이 유효하다.

 

(2) 배수 관계와 그리디 전략의 유효성

• 큰 가치의 동전을 최대한 많이 사용해야 최소 개수가 된다.

• 예를 들어, 목표 금액이 800이고 동전이 500, 100, 50, 10일 때:

• 500원 동전 1개 → 나머지 300

• 100원 동전 3개 → 나머지 0

• 총 4개의 동전으로 해결 (최적해)

 

---

 

2. 자료구조 및 변수 분석

(1) 배열 (Array)

int[] coins = new int[n];

 

• 역할: 동전의 가치를 저장한다.

• 크기: n (동전 종류의 개수)

• 배열 초기화: 사용자 입력으로 초기화.

• 접근 방식: 큰 가치의 동전부터 사용하기 위해 인덱스 idx를 뒤에서부터 접근한다.

 

(2) 변수 분석

int n = scanner.nextInt();  // 동전 종류의 개수
int k = scanner.nextInt();  // 목표 금액
int ans = 0;                // 사용한 동전의 최소 개수
int idx = n-1;              // 가장 큰 동전부터 접근하기 위한 인덱스

 

• n: 동전 종류의 개수.

• k: 만들고자 하는 금액.

• ans: 최소 동전 개수를 저장.

• idx: 배열 coins의 마지막 인덱스부터 시작.

• 가장 큰 동전부터 사용하기 위해 idx = n-1로 설정.

• 그리디 전략의 핵심.

 

---

 

3. 주요 로직 분석

(1) 큰 동전부터 탐색

while(idx >= 0) {
    int coin = coins[idx];

 

• 인덱스를 뒤에서부터 접근하여 큰 동전부터 사용한다.

• 그리디 알고리즘의 기본 전략: 가장 큰 값을 우선적으로 선택.

 

(2) 동전 사용 여부 판단 및 개수 계산

if(coin > k) { 
    idx--; 
    continue;
}

 

• 현재 동전이 목표 금액보다 크면 사용할 수 없으므로, 다음 작은 동전으로 넘어간다.

 

ans += k / coin;
k %= coin;
idx--;

 

• 현재 금액 k에 대해 현재 동전을 최대한 많이 사용.

• k / coin → 현재 동전으로 만들 수 있는 최대 개수

• k %= coin → 남은 금액 계산

• 큰 동전부터 최대한 많이 사용하는 전략이기 때문에 최소 개수를 보장한다.

 

---

 

4. 시간 복잡도 및 공간 복잡도

(1) 시간 복잡도

• O(n):

• 동전 종류의 개수 n만큼 반복.

• 각 동전마다 k / coin과 k % coin 계산은 상수 시간이므로 O(1).

• 총 시간 복잡도: O(n)

 

(2) 공간 복잡도

• 배열 coins에 n개의 동전 정보 저장 → O(n)

• 기타 변수(int)는 상수 공간만 사용.

• 총 공간 복잡도: O(n)

 

 

 

---

5. 정리 및 특징

• 그리디 전략을 사용해 최적해를 구하는 문제.

• 큰 동전부터 최대한 많이 사용하는 전략.

• 배수 관계 덕분에 그리디 방식이 유효하다.

• 시간 복잡도 O(n), 공간 복잡도 O(n)으로 효율적이다.

• 배열과 그리디 알고리즘의 기본 개념을 이해하기 좋은 예제다.

 

 

 

---

6. 동전들이 배수관계가 아니었다면?

• 배수 관계가 아닌 경우에는 그리디 방식이 최적해를 보장하지 않으므로, 다이나믹 프로그래밍(DP) 접근법이 필요하다.

• 예를 들어, 동전이 1, 3, 4일 때 6을 만드는 경우, 그리디는 4 + 1 + 1 = 6(3개)이지만, 3 + 3 = 6(2개)이 최적해다.

• 이 경우 DP 방식으로 해결할 수 있다.