[JAVA][Baekjoon] 11047번 동전 0

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

---

📌 접근 방식

1️⃣ 탐욕적 선택 속성

• 가장 큰 동전부터 최대한 사용하면, 남은 금액을 최소화할 수 있.
• 동전의 가치가 오름차순이며, 각 동전은 이전 동전의 배수이므로 탐욕적 선택이 최적해를 보장한다.

2️⃣ 문제 풀이 전략

• 동전 배열을 내림차순으로 탐색하며, 현재 동전으로 만들 수 있는 최대 개수를 구함
• 남은 금액을 업데이트하며 반복

[알고리즘] 그리디 알고리즘(Greedy Algorithm)

---

✅ PASS CODE

import java.io.*;          // 입력/출력 처리
import java.util.Arrays;   // 배열 정렬
import java.util.StringTokenizer; // 입력 분리

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[] A = new int[N]; // 동전 배열

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            A[i] = Integer.parseInt(st.nextToken()); // 동전 가치 입력
        }

        // 동전 개수 계산
        int count = 0; // 필요한 동전 개수
        for (int i = N - 1; i >= 0; i--) { // 큰 동전부터 탐색
            if (A[i] <= K) { // 현재 동전으로 K를 만들 수 있는 경우
                count += K / A[i]; // 해당 동전의 최대 개수 추가
                K = K % A[i]; // 남은 금액 갱신
            }
        }

        // 결과 출력
        System.out.println(count);
    }
}

1️⃣ 최적 동전 선택:

• 가장 큰 동전부터 순차적으로 확인하며, 해당 동전으로 만들 수 있는 최대 개수를 count에 추가합니다.

2️⃣ 남은 금액 처리:

• 현재 동전으로 처리한 금액을 제외한 나머지 금액(K)를 계산합니다.

---

반응형

😊 느낀 점

처음 문제를 보고 그리디 알고리즘을 사용하면 되겠다라고 생각했더니 간단하게 풀 수 있었다.

이 문제에서 핵심은 금액이 큰 동전부터 차례로 사용하면서 목표 금액(K)을 나누는 방식이다. 큰 동전을 먼저 사용하면 남은 금액을 최소화할 수 있고, 덕분에 동전의 개수를 최소화할 수 있었다. 금액을 나눌 때 작은 동전부터 탐색했다면 불필요한 연산이 많아졌겠지만, 큰 동전부터 탐색하면서 나누고 남은 금액만 처리하는 방식 덕분에 최소한의 연산으로 최적의 결과를 얻을 수 있었다. 😊