✨ 문제

백준 11047번

📍 알고리즘 유형

그리디(greedy) 알고리즘

✨ 풀이

입력된 N종류의 동전의 가치 합으로 K를 만드는 것이 이 문제의 목표이다.
문제 풀이 핵심

동전 개수의 최솟값, 즉, 가치가 큰 동전이 최대한 많이 포함되어야 한다!

🔻 단, K보다 큰 가치를 가지는 동전은 사용할 수 없다.
👉🏻 N종류 동전들의 가치를 입력을 받을 때 K보다 큰 값이 입력되면 배열에 저장하지 않음으로써 후보들에서 배제한다.
🔻 가치가 큰 것이 최대한 많이 포함되어야 한다!
👉🏻 오름차순으로 입력되고, 이를 ArrayList 객체에 저장하므로 먼저 맨 마지막 요소(가치가 제일 큰, 단, K보다 작거나 같은)부터 "K / 가치"를 하여 그 동전이 최대 몇 개 들어갈 수 있는지 계산한다. 이후 K - (그 개수 * 가치)를 하고 다음으로 큰 가치로 넘어가서 같은 계산을 반복한다.

✨ 코드

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

public class Main {
    static int N, K, minCnt;
    static ArrayList<Integer> Val;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

        Val = new ArrayList<>();
        // 입력받으면서 K - 가치 < 0가 되는 위치를 찾고, 그 위치 - 1을 변수에 저장한다. --> 가치를 만들 때 가장 큰 값으로 채우는 것이 중요하기 때문
        for(int i = 0; i < N; i++){
            int value = Integer.parseInt(br.readLine());
            if(K - value > 0){
                Val.add(value);
            } else if(K - value < 0){
            } else{
                minCnt = 1;
            }
        }

        if(minCnt == 1){
            System.out.println(minCnt);
            return;
        }
        minCnt = 0;

        // 이제 저장된 배열에서 거꾸로 가면서(--> 큰 가치의 동전부터 최대 개수로 세야 하기 때문) 최대 몇 개 넣을 수 있는지 세기
        for(int i = Val.size()-1; i >= 0; i--) {
            if (K - Val.get(i) >= 0) {
                minCnt += (K / Val.get(i));
                K -= Val.get(i) * (K / Val.get(i));
            }
            if(K == 0){
                break;
            }
        }
        System.out.println(minCnt);
    }
}

👩🏻‍💻 오늘의 이야기

오늘 발견한건데 벨로그에 다크모드가 생겼다!!!(나만 오늘 안 건가..?)