백준 11047번 : 동전 0(Java)

그리디 알고리즘(Greedy Algorithm)에 대해서 알게되었습니다. 문제 해결에서 연속되는 선택들중 이전 선택이 이후의 선택에 영향을 주지 않는경우(독립적)에 사용한다고 합니다. 또한 전체 문제에서 최적화된 해가 부분 문제에서에도 최적화되어야 합니다. 해당하는 조건을 만족하는 경우 그리디 알고리즘으로 문제풀이가 가능합니다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class p11047 {
 
	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());
		
		// 동전의 가치의 갯수만큼 intger배열 선언
		int[] coin = new int[N];
		
		for(int i = 0; i < N; i++) {
			// 코인의 가치를 입력받는다.
			// 오름차순으로 받는다.
			coin[i] = Integer.parseInt(br.readLine());
		}
		
		int count = 0;
		
		// 오름차순으로 이루어진 coin배열에서
		// 역순으로 가장 큰 가치의 코인부터 입력한다.
		for(int i = N - 1; i >= 0; i--) {
			// 현재 동전의 가치가 K보다 작거나 같아야지 구성가능하다.
			if(coin[i] <= K) {
				// 현재 가치의 동전으로 구성할 수 있는 개수를 더해준다.
				count += (K / coin[i]);
				// 거스르고 남은 값 K에 저장
				K = K % coin[i];
			}
		}
		System.out.println(count);
	}
 
}