[JAVA] 백준 11047 동전 0

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

11047번: 동전 0

 

 

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

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

 

문제 풀이 

 

- 그리디 알고리즘을 활용한 동전 거스름돈 문제 

- 동전 거스름돈 문제를 해결하는 가장 간단하고 효율적인 방법은 남은 액수를 초과하지 않는 조건하에 '욕심내어' 가장 큰 액면의 동전을 취하는 것

 

- 동전의 액면이 500원, 100원, 50원, 10원, 1원 일때

입력 : 거스름돈 액수 W
출력 : 거스름돈 액수에 대한 최소 동전 수 
change = W , n500=n100=n50=n10=n1 =0

while(change>=500)
	change = change-500, n500++ //500원짜리 동전 수를 1증가 
while(change>=100)
	change = change-100, n100++ //100원짜리 동전 수를 1증가 
while(change>=50)
	change = change-50, n50++ //50원짜리 동전 수를 1증가 
while(change>=10)
	change = change-10, n10++ //10원짜리 동전 수를 1증가 
while(change>=1)
	change = change-1, n1++ //1원짜리 동전 수를 1증가 

return(n500+n100+n50+n10+n1) //총 동전 수를 리턴

 

 

정답 

 

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Main {
    static int count=0;
    
    public static void main(String[] args)throws IOException
    {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        
        int coin[] = new int[n];
        

        for(int i=0; i<n; i++)
        {
        	st= new StringTokenizer(br.readLine());
        	coin[i] = Integer.parseInt(st.nextToken());
        }
       
        for(int i=n-1; i>=0; i--)
        {
        	if(coin[i]<=k)
        	{
        		count+=(k/coin[i]);
        		k = k%coin[i];
        	}
        }
        
        bw.write(count+"");
        
        bw.flush();
        bw.close();
        
    }
}