[BOJ] 11047 - 동전 0(Java)

문제

 

📝 설명

주어진 동전 종류를 활용해서 목표 금액 K를 만족하는 최소 동전 갯수를 구하면 되는 문제였습니다. 문제가 너무 쉽게 풀려 다른 접근법이 있을까 찾아보았는데, 비슷한 풀이가 많았네요.

🛠 사용 기술

• 그리디 알고리즘

 

---

Approach 1 ❌

• 운좋게 한 번에 성공했습니다..!

 

---

Approach 2 ⭕

🔍 접근법

• 입력받은 값을 저장할 자료구조를 선택해야했는데, N의 최댓값이 매우 작은 10이어서 Array를 선택했습니다.
• 동전은 큰 값이 작은 값의 배수이므로, 가장 큰 동전부터 사용하면 최소 개수를 보장합니다 (그리디 활용).
• 목표 금액 K를 현재 선택한 동전으로 나눌 수 없다면 다음 동전을 선택하고, 나눌 수 있다면 몫은 카운트에 추가하고, 나머지를 K로 새로 갱신해줍니다!

💻 코드

package org.example;

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

public class Main {
    static int N, K;
    static int[] coins;
    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());

        coins = new int[N];

        for(int i=N-1; i>=0; i--){
            coins[i] = Integer.parseInt(br.readLine());
        }

        int coin_cnt=0;

        for(int i=0; i<N; i++){
            if(!(K / coins[i] == 0)){ //나눌 수 있는 경우
                coin_cnt += K/coins[i];
                K = K%coins[i];
            }
        }

        System.out.println(coin_cnt);
    }
}

 

---

느낀 점 및 메모 💡

• 그리디 문제는 “조건”을 잘 파악하면 단순화된다는 것을 알게 됐습니다. 여기서는 배수 관계가 조건입니다!
• 그리디 알고리즘을 많이 풀어봐야될 것 같습니다