백준 11047번: 동전 0 [JAVA]

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

2839번: 설탕 배달

• 풀이

Ai는 Ai-1의 배수이기 때문에 무조건 큰 가치의 동전을 내는 것이 유리하다.

따라서 가치가 큰 순서부터 최대한 많이 내면 최솟값을 구할 수 있다.

• 코드

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

public class Main {
	static int N, K;
	static int A[];
	static int cnt;
	
	static void findMin() {
		for (int i=N-1; i>=0; i--) {
			if (K>=A[i]) {
				int n = K/A[i];
				K = K - A[i]*n;
				cnt+=n;
			}
			if (K==0) break;
		}
	}

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		
		// 입력
		N = Integer.parseInt(st.nextToken());
		K = Integer.parseInt(st.nextToken());
		
		A = new int [N];
		for (int i=0; i<N; i++) A[i] = Integer.parseInt(bf.readLine());
		
		// 최솟값 찾기
		findMin();
		
		// 출력
		System.out.println(cnt);
	}
}