[백준 11047번] 동전 0

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-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

 

문제 접근

문제를 보고 어떤 알고리즘인지 떠올리는 게 중요하다고 생각합니다. 이 문제는 그리디 알고리즘의 첫 번째 문제로 그리디 알고리즘 소개와 대표적인 문제 유형을 다뤄보도록 하겠습니다.

 

그리디 알고리즘은 이름에서 알 수 있듯 각 단계별 (현재 선택에서) 최선의 선택을 해나가는 알고리즘입니다.

주의할 점은 항상 최적의 해를 도출해내는 것은 아닙니다.

 

특징으로는 2가지가 있습니다.

1. 이전의 탐욕 선택이 이후의 선택에 영향을 주지 않는다.

2. 전체 최적해가 부분 문제에 대해서도 최적해를 만족한다.

=> 각 단계마다 최적 선택을 하기 때문에 근사 해를 구하는 속도가 매우 빠릅니다.

 

 

대표적인 문제들은 무엇일까요?

거스름 돈 문제, 활동 선택, 최소 신장 트리 문제 등이 있습니다.

 

---

 

이 문제로 다시 돌아와서 입력 예시 1,2를 봤을 때 공통점을 발견할 수 있습니다.

각 동전들은 서로 배수 관계에 있는 것을 알 수 있습니다.

이렇게 배수 관계에 놓여있을 때 풀리는 대표적인 문제는 이번 문제 같은 경우와, 거스름돈 문제가 있습니다.

 

 

그럼 여기에 그리디 알고리즘(각 단계별 최적해)은 어떻게 적용하는 걸까요?

K원을 만들 때 최소한의 개수를 이용해야 하므로 가장 큰 가치를 지닌 동전부터 선택하되 만약 동전의 가치가 K원보다 크면 넘어가는 식으로 코드 구현을 해보겠습니다.

 

어떤 동전이 몇 개인지까지 구하는 것이 아닌 최소 개수를 구하는 것이므로 코드가 한결 간결해질 것 같습니다. 

 

// 동전을 입력받을 배열을 선언합니다.
int[] coin = new int[n]

// 출력할 count를 선언합니다.
int count = 0;

// 가치가 큰 동전부터 선택해 나갈 것이므로 for문을 뒤에서부터 실행시킵니다.
// 동전의 갯수는 나누기를, 다음 단계로 넘어가기위해 K는 나머지로 갱신합니다.
for(int i=n-1; i>=0; i--) {
	
    // 만약 동전이 K보다 크다면 넘어가야하므로 작을시에만 들어오게합니다.
    if(coin[i] <= K) {
    	count += (K / coin[i]);
        K = (K % coin[i]);
    }
}
System.out.println(count);

📢  동전의 개수는 나누기를, 다음 단계로 넘어가기 위해 K는 나머지로 갱신합니다.

 

💡 배수가 있는 문제에서 / 와 % 를 떠올리기!

 

 

이제 위 코드를 활용해서 전체적인 코드를 구현해보겠습니다. (성공 코드)

import java.util.*;

public class Coin {

	public static void main(String[] args) {
		// 입력
		Scanner kb = new Scanner(System.in);
		int N = kb.nextInt();
		int K = kb.nextInt();
		// for문을 돌면서 n개의 입력값을 배열에 넣기
		// 배열 선언
		int[] coin = new int[N];
		for(int i=0; i<N; i++) {
			coin[i] = kb.nextInt();
		}
		// 출력할 count 선언
		int count = 0;
		// 배열의 뒤부터 선택, 동전의 가치가 K보다 작을 경우만 선택
		for(int i=N-1; i>=0; i--) {
			if(coin[i] <= K) {
				count += (K / coin[i]);
				K = (K % coin[i]);
			}
		}
		System.out.println(count);
	}

}

 

 

 

성공하기 전에 실수 한 점을 언급해보자면,

주로 배열의 첫 번째부터 선택을 하다 보니 끝부터 도는 경우는 없었기 때문에

for문을 작성할 때 조건식에서 실수가 있었습니다. 물론 변수 초기화도 신경 써서 작성해야 합니다. 

 

for (int i=N-1; i<=0; i--) → for(int i=N-1; i>=0; i--)
하나씩 줄어드는 것이므로 N-1 →  0을 생각해야 합니다. 

 

 

---

 

 

대략적인 코드 구현 후 실행할 때  

java.lang.ArrayIndexOutOfBoundsException: Index N out of bounds for length N

에러가 자주 등장했습니다.

 

배열을 사용할 때 범위를 의식적으로 생각하면서 차근차근 적어보는 습관을 들여야겠습니다^^