[백준-11047번 자바/java] 동전 0 _디버깅의 눈물

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

11047번: 동전 0

 

 

 

 

동전 0 성공

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

98338

51501

39934

51.839%

문제

준규가 가지고 있는 동전은 총 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

 

 

 

 

---

 

 

체크 포인트

 

1. 그리디 알고리즘(Greedy Algorithm) 이용

 

-현재의 가장 최적의 답을 선택해 적합한 결과를 도출해내는 '그리디 알고리즘'을 이용하는 문제이다.

-그리디 알고리즘의 대표적 문제 유형으로는 활동 선택 문제나 거스름돈 문제 등이 있다.

-동전의 가치가 서로 배수 관계를 이루는 것은 거스름 돈이나 동전교환 문제에서 자주 등장하는 조건이다.

-동전의 종류에는 1원이 무조건 존재하므로, 교환되지 않는 경우는 존재하지 않는다.

 

 

 

    	// 큰 수의 동전부터 탐색 시작
    	for(int i=N-1; i>=0; i--){
    		// 목표 금액이 해당 동전보다 크거나 같다면,
    		if(coins[i]<=K){
    			// K를 해당 동전으로 나눈 몫을 개수에 추가하고,
    			count += K/coins[i];
    			// K는 해당 동전으로 나눈 나머지값 처리
    			K = K%coins[i];
    		}
    	}

 

 

-그리디 알고리즘에 따라, 현재 가장 큰 수의 동전을 최대한 많이 사용해 거슬러준다면, 최소의 동전 개수로 거스름 돈을 완성할 수 있다.

 

-예제1)의 경우, 아래 과정을 통해 4+2=6개의 정답을 도출할 수 있다.

1)4200원 보다 작거나 같은 동전 중에 가장 큰 1000원 동전을 4개 사용하고 200원이 남는다.

2)200원 보다 작거나 같은 동전 중에 가장 큰 100원 동전을 2개 사용하고 0원이 남는다.

 

-예제2)의 경우, 아래 과정을 통해 4+1+2+1+4=12개의 정답을 도출할 수 있다.

1)4790원 보다 작거나 같은 동전 중에 가장 큰 1000원 동전을 4개 사용하고 790원이 남는다.

2)790원 보다 작거나 같은 동전 중에 가장 큰 500원 동전을 1개 사용하고 290원이 남는다.

3)290원 보다 작거나 같은 동전 중에 가장 큰 100원 동전을 2개 사용하고 90원이 남는다.

4)90원 보다 작거나 같은 동전 중에 가장 큰 50원 동전을 1개 사용하고 40원이 남는다.

5)40원 보다 작거나 같은 동전 중에 가장 큰 10원 동전을 4개 사용하고 0원이 남는다.

 

 

 

 

 

 

 

풀이

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public  class Main {
	
	static int N,count;
	
	static int[] coins;
	
    public static void main(String[] args) throws IOException {
    	
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	StringTokenizer st = new StringTokenizer(br.readLine(), " ");

    	N = Integer.parseInt(st.nextToken());
    	
    	// 목표 금액
    	int K = Integer.parseInt(st.nextToken());
    	
    	// 거스름돈 동전의 종류를 담아주는 배열
    	coins = new int[N];
    	
    	// 거스름돈 종류 입력
    	for(int i=0; i<N; i++){
        	st = new StringTokenizer(br.readLine());
    		coins[i] = Integer.parseInt(st.nextToken());
    	}
    	
    	
    	solution(K);
    	
    	
    }
    
    
    static void solution(int K){
    	
    	// 큰 수의 동전부터 탐색 시작
    	for(int i=N-1; i>=0; i--){
    		// 목표 금액이 해당 동전보다 크거나 같다면,
    		if(coins[i]<=K){
    			// K를 해당 동전으로 나눈 몫을 개수에 추가하고,
    			count += K/coins[i];
    			// K는 해당 동전으로 나눈 나머지값 처리
    			K = K%coins[i];
    		}
    	}
    	
    	System.out.println(count);
    }
    

} // end of Main