[백준] 11047 실버4 동전0 java 풀이

1. 문제 설명 📌

문제 링크

설명이 직관적이라 추가 설명 생략

2. 접근 방식 🗃️

KEY WORD: Greedy Algorithm

동전 수가 무한하기 때문에 Greedy 알고리즘을 적용하면 된다. Greedy 알고리즘은 매 순간 최적의 선택을 하는 것이다. 여기서 최적의 선택은 가능한한 큰 단위의 동전을 사용하여 동전 개수를 줄이는 것이다. 따라서 내림차순으로 동전 단위를 하나씩 훑으며, K원을 최대한 큰 단위의 동전으로 차감한다.

1. 내림차순으로 동전 조회
2. 만약 현재 조회 중인 동전으로 K원을 나눌 수 있다면? 나눈 몫만큼 동전을 사용 가능한 것임으로 몫을 답에 누적시킴
3. K원은 (해당 동전의 단위 x 몫) 만큼 차감되었으므로, 나머지만큼만 남아있는 것이다. 따라서 K = K%단위로 갱신한다.
4. 1,2,3번을 K == 0이 될때까지 반복

3. 코드 소개 🔎

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 [] units = new int [N];

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

        int ans = 0;
        for(int i = N-1; i >= 0; i--){
            if(K/units[i] != 0) {
                ans += K/units[i];
                K = (K%units[i]);
            }
            if(K == 0) break;
        }
        System.out.println(ans);
    }
}

4. 배운 것들 🎯

K원을 갱신하는 과정

 K = (K%units[i]);

이 부분을 처음에는

 K -= (K/units[i])*units[i];

이렇게 했었는데, 다른 사람의 풀이를 보고 '아... 나머지만 남기면 되는구나! '하고 깨달아서 다시 고쳤다.

Greedy 알고리즘에 대한 감을 익혔다.