백준 11047번 - 동전 0

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

11047번: 동전 0

 

다음 문제는 K 라는 가격을 동전의 가치로 만들어야 하는데 그 중에서 동전의 개수가 최소값이 되는 개수를 출력해야한다.

만약 K가 4200원일 때 (1000원 x 4개) + (100원 x 2개) 해서 6이 출력되어야 한다. 

만약 K가 4790원일 때 (1000원 x 4개) + (500원 x 1개) + (100원 x 2개) + (50원 x 1개) + (10원 x 4개) 해서 12이 출력되어야 한다.

 

다음 아래 그림은 K가 4790원일 때 구하는 방법이다.

 

 

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		int arr[] = new int[N];
		int copy[] = new int[N];
		
		int min=0;
		int res=K;
		int index=0;
		int count=0;
		
		for(int i=0;i<N;i++)
		{
			arr[i] = sc.nextInt();
		}
		while(res!=0)
		{
			for(int i=0;i<N;i++)
			{
				copy[i] = res/arr[i];
			
				if(copy[i]>0)
				{
					min = Math.min(copy[i],copy[0]);
					index=i;
				}
			}
			res = res-arr[index]*min;
			count+=min;
		}
		System.out.println(count);
	}
}