(Java) 백준 11047 - 동전 0

그리디 알고리즘을 이용하는 문제이다.

먼저 가장 큰 단위의 동전으로 낼 수 있을 만큼 내고

다음 동전의 단위로 넘어가서 또 낼수 있을 만큼 내면 된다.

이렇게 k의 값을 줄여나가다 보면 필요한 동전의 최소 개수가 나오게 된다.

예전에 그리디 알고리즘을 처음 접했을때 비슷한 문제를 풀어봤던 기억이 나서 쉽게 풀었다.

 

 

---

최종 코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        int answer = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // n과 k를 분리하기 위한 StringTokenizer
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        // k를 담는 배열
        Integer[] coin = new Integer[n];
        for (int i = 0; i < n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
        // 내림차순으로 정렬
        Arrays.sort(coin, Collections.reverseOrder());
        // 가장 큰 동전의 단위로 낼수 있는 만큼 내고 다음 동전 단위로 넘어가기
        int i = 0;
        while (k != 0) {
            if(k - coin[i] >= 0) {
                k = k - coin[i];
                answer++;
            } else {
                i++;
            }
        }
        System.out.println(answer);
    }
}

 

내림차순으로 정렬을 하지않고 while문을 for문으로 바꿔서 풀면 속도가 더 빠르다.

 

다른 방식 코드

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 {
		int answer = 0;
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // n과 k를 분리하기 위한 StringTokenizer
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        // k를 담는 배열
        Integer[] coin = new Integer[n];
        for (int i = 0; i < n; i++) {
            coin[i] = Integer.parseInt(br.readLine());
        }
		// for문 사용
		for(int i=n-1;i>=0;i--) {
			if(k>=coin[i]) {
				answer+=k/coin[i];
				k=k%coin[i];
			}
		}
		System.out.println(answer);
	}

}