자바(Java) 알고리즘 문제풀이 동전0 [백준 / 그리디]

출처 - 구글 이미지

 

11047번: 동전 0

 

 

---

 

 

풀이 코드

전형적인 그리디 문제로 가능한 큰 동전으로 연산하며 가능한 최소한의 동전 갯수를 구하는 문제이다.

그리디로 접근 시 주의해야할 점이 있는데, 문제 설명을 보면 (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 라고 명시

되어있는 것을 볼 수 있다. 쉽게 말하자면 각 동전의 가치는 서로 배수관계에 있다는 뜻이며 이 입력이 보장되기 때문에 그리디로 문제를

풀이할 수 있는 것 !

 

만약 동전의 가치 입력 부분에서 저런 입력의 보장이 없다고 하고, 100, 400, 500 이런 식으로 입력이 된다고 하면, 그리디로 문제를

풀 수가 없다. 만약 동전의 종류 = 4, 원하는 K 값 = 14, 각 동전의 가치 = 1, 4, 5, 6 이라고 하면, 필요한 최소한의 동전은 5(2개), 4(1개)

총 3개지만, 그리디로 접근하면 6(2개), 1(2개) 총 4개가 리턴된다. 1, 4, 5, 6 이 배수의 관계에 있지 않기 때문에 😅

 

풀이 중에 어떤 식으로 구현할지 주석으로 작성했다.

package backjoonsliver;

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

public class Boj11047 {
    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());
        List<Integer> coins = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            coins.add(Integer.parseInt(br.readLine()));
        }

        // 큰 코인부터 검사하는게 빠르니까, 배열 뒤집기
        Collections.reverse(coins);

        // 뒤집은 코인 배열에서 k 보다 작은 숫자면서 제일 큰 코인으로 빼주기
        int count = 0;
        int tmp = 0;

        // 알맞게 큰 코인을 찾았다면 해당 코인을 저장한다.
        for (int coin : coins) {
            if (coin <= k) {
                tmp = coin;
            } else {
                continue;
            }

            // 연산을 수행하면서 k가 tmp 보다 더 커야 뺄 수 있으니까
            // <= 를 해줘야 100 남았을 때 100을 빼주고 하지 아니면 50, 10 으로 넘어간다.
            while(tmp <= k) {
                k -= tmp;
                count ++;
            }
        }

        System.out.println(count);
    }
}

// 동전 0
/* 1 <= N <= 10 / 1 <= K <= 1억
* 동전 총 N 종류, 각각의 동전 무한대로 소유
* 각 동전을 적절히 섞어서 가치의 합을 K 로 만들려고 한다.
* 이때 필요한 동전 갯수의 최소값을 구해라.
* */

// 10(n) 4200(k)
/* 동전의 가치
* 1
* 5
* 10
* 50
* 100
* 500
* 1000
* 5000
* 10000
* 50000
* */