(백준) 11047번: 동전 0 - 세상 스케치

쉬운 목차

문제

준규가 가지고 있는 코인은 총 N종이며, 각각의 코인을 많이 가지고 있습니다.

우리는 코인을 적절하게 사용하여 그 가치의 합이 K와 같도록 노력합니다.

그 시간에 필요한 최소 동전 수를 찾는 프로그램을 작성하십시오.

기입

N과 K는 첫 번째 줄에 표시됩니다.

(1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

'추천 관련글,

두 번째 줄부터 N개의 줄에는 코인의 Ai 값이 오름차순으로 주어진다.

(1 ≤ AI ≤ 1,000,000, A1 = i ≥ 2인 경우 1, Ai는 Ai-1의 배수)

누르다

첫 번째 라인은 K를 획득하는 데 필요한 최소 코인 수를 처리합니다.

예시 입력 1

예제 출력 1

샘플 입력 2

샘플 출력 2

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

public class Main {
	public static void main(String() args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		
        // 동전 개수를 담을 변수
		int count = 0;

		int() arr = new int(N);

		for(int i=0;i<N;i++) {
			arr(i) = Integer.parseInt(bf.readLine());
		}
		
        // 동전 개수가 최소값으로 나와야하므로 K보다 작은 값 중에 가장 큰 수로 나눈다.


        // 그리고 나눈 나머지값을 K에 다시 담고 동일하게 나눈다.

 
        // 배열이 오름차순으로 담기므로 배열 뒤에서 부터 시작한다.


		for(int i=N-1;i>=0;i--) {
			if(K>=arr(i)) {
				count+=(K/arr(i));
				K = (K%arr(i));
			}
		}
		System.out.println(count);
	}
}

간단한 당기기