[백준] 11047 : 동전 0 - JAVA

문제분석

전형적인 그리디 알고리즘 문제
그리디 알고리즘을 풀 수 있도록 뒤의 동전 가격 A(i)가 앞에 나오는 동전 가격 A(i-1)의 배수가 된다는 조건을 부여했다.
가장 가격이 큰 동전부터 차례대로 사용하면 된다.

1. 가장 가격이 큰 동전부터 탐색을 시작하고, K보다 가격이 작거나 같은 동전이 나올때까지 탐색한다.
2. 현재 동전의 가격으로 K를 나눈다.
   -> 몫 : 동전 개수에 더한다.
   -> 나머지 : K값으로 갱신한다.
3. 나머지가 0이 될 때까지 반복한다.

제출코드

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 br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int[] coin = new int[N];
		for(int i=0; i<N; i++) {
			coin[i] = Integer.parseInt(br.readLine());
		}
		int count =0;
		int sum =0;
		for(int i=N-1;i >= 0; i--) {
			while(sum + coin[i] <= K) {
				sum += coin[i];
				count++;
			}
		}
		System.out.println(count);
	}
}

다른풀이

나눗셈의 몫과 나머지를 이용해서 더 빠르게 구할 수 있다.

다른 부분의 코드는 로직이 동일하고 간단하기떄문에, 해당 부분만 코드를 작성하겠다.

for(int i=N-1;i >= 0; i--) {
	if(A[i] <= K) {
    	count += (K/A[i]);
    	K = K % A[i];
}