백준 11047번 ) 동전 0 (java)

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

11047번: 동전 0

 

문제

 

그리디알고리즘 문제였다. 그리디 알고리즘이란, 탐욕 기법으로 가장 큰것부터 탐해가면서 문제를 풀어나가는 것이었다.

따라서 주어지는 동전의 가치가 오름차순으로 주어지기 때문에, 가치가 큰 순서 즉 배열의 마지막부터 탐색해나가면서 동전의 개수를 최소화하여 택한다.

 

또 문제에서 주어지는 조건

A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수

이 부분이 있어서, 금액에서 나머지를 계산하여 밑의 동전 크기와 맞아떨어지는 것으로 계산할 수 있다.

 

 

풀이

import java.io.*;
import java.util.*;

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];
		int count = 0;

		for(int i =0; i < N; i++){
			coin[i] = Integer.parseInt(br.readLine());
		}

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

		System.out.println(count);

    }
}

 

느낀점

오랜만에 다시 코테 문제풀려고하니까 기억이 잘 안난다.

내맘대로 클래스 이름 선언해서 풀다가 백준에 Main 이라고 변경 안해서 컴파일에러 났었다. 변경하는 것 잊지 말자!