[백준/Java] 11047번: 동전 0

문제 정보

제목 : 동전 0

번호 : 11047번

사용 언어 : Java

문제 링크

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

11047번: 동전 0

 

시간 제한	메모리 제한
1 초	256 MB

 

문제

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

 

입출력 예제

---

나의 풀이

동전의 종류 N, 가치의 합 K를 각각 저장합니다. N번 반복하는 for루프를 이용해 한줄의 입력을 받아 정수형으로 형변환후 K와 비교합니다. K보다 크면 break하여 반복을 종료하고, 작으면 ArrayList에 저장합니다. ArrayList를 뒤집고, 하나씩 접근하는 for루프를 생성하여 count의 수를 구합니다. 반복이 끝나면 count를 출력합니다.

 

코드

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

public class Main {
	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());
		
		// 동전의 가치가 합인 K보다 작으면 ArrayList에 저장
		ArrayList<Integer> coin = new ArrayList<>();
		for(int i=0; i<N;i++) {
			int A = Integer.parseInt(br.readLine());
			if(A > K)
				break;
			coin.add(A);
			
		}
		Collections.reverse(coin);
		
		int count = 0;
		for(int c : coin) {
			if( c <= K ) {
				count += (K/c);
				K %= c;
			}
		}

		bw.write(count+"\n");
		
		bw.flush();
		bw.close();
		br.close();
	}
}