Baekjoon11047: 동전 0

동전 0

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

1 초

256 MB

63302

33632

26262

52.513%

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

풀이

현재 K원에서 만들 수 있는 동전 중 최대가치인 것을 골라내고 다시 남은 돈에서 낼 수 있는 동전 가치 중 최대인 것을 고른다.

 

제한조건

동전의 가치는 배수로 나타나기 때문에 무조건 큰 단위의 동전을 내는 것이 유리하다. 300원 500원 이런식이 아닌 300원 600원과 같은 배수의 형태이기 때문이다. 

반복문

현재 가지고 있는 돈 K보다는 작지만 동전 가치 중에서는 가장 큰 동전을 고르면 된다. 이를 위해 배열에 크기가 큰 동전 순으로 배치하고

K보다 작아질 때 바로 그 동전 가격으로 K를 나누어서 지불하고 나머지를 다시 K에 넣어 연산을 반복한다

import java.util.Scanner;
import java.util.StringTokenizer;
public class Main {
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt(), K=sc.nextInt();
		int[] coin = new int[N];
		for(int i=N-1;i>=0;i--){ //크기가 큰 동전부터 배열에 배치한다
			coin[i]=sc.nextInt();
		}
		int sum=0;
		for(int i=0; i<N;i++) {
			if(K>=coin[i]) {  //동전의 크기가 현재 남은 돈 K보다 작아지는 순간 나눈다
				sum+=K/coin[i]; //동전의 개수를 기록한다
				K%=coin[i]; //나눈 나머지를 다시 k에 집어넣는다
			}
		}
		System.out.println(sum);
	}
}