[백준] BOJ 11047 동전 0 자바 풀이

 

www.acmicpc.net/problem/11047

11047번: 동전 0

문제 해석

문제

준규가 가지고 있는 동전은 총 N종류이고, 각각의 동전을 매우 많이 가지고 있다.

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000)

둘째 줄부터 N개의 줄에 동전의 가치 Ai가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

출력

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

문제 풀이

무식하게 풀 수 있을까?

무식하게 풀 수 있을 것 같다!

가장 적게 동전을 사용하면 되는 문제이므로,

1️⃣ 입력 중 가장 큰 값부터 검사해서 만들어야 하는 값보다 화폐가 작으면 마이너스, 아니면 인덱스를 줄임!

2️⃣ 마이너스 할 때마다 동전 개수 count 올리기

3️⃣ 0 될때까지 반복 후 마지막에 count 출력

 

무식하게 풀었음!

 

💰 그리디 알고리즘 이용

🍕 Greedy Algorithm은 문제를 해결하는 과정에서 그 순간순간마다 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식이다.

그리디 알고리즘은 아래 두 조건이 충족되었을 때 잘 작동한다.

 

1️⃣ 탐욕스러운 선택 조건

앞의 선택이 이후의 선택에 영향을 주지 않는다.

 

2️⃣ 최적 부분 구조 조건

문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결 방법이다.

 

그리디 알고리즘 이용한 코드는 다른 사람 코드를 참고했다.

풀이는 아래 두가지 조건을 이용!

1. 가장 큰 액수부터 계산!

2. 나누는 돈 / 현재 지폐 에서 몫은 지폐 사용량, 나머지는 다음 화폐로 나눌 금액이 된다.

 

import java.io.FileInputStream;
import java.util.*;
import java.util.stream.*;

class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(new FileInputStream("input.txt"));
        // Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int count =0;
        int[] arr=  new int[N];
        for(int i=0; i<N; i++){
            arr[i] = sc.nextInt();
        }

        for(int i = N-1; i>=0; i--){
            if(M>=arr[i]){
                count += M/arr[i];
                M = M%arr[i];
            }

        }

        System.out.println(count);


    }

}

 

문제 풀이 코드

package Greedy;

import java.util.Scanner;

public class BOJ11047 {
    static int[] wallet;
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int N = s.nextInt();
        int K = s.nextInt();

        wallet = new int[N];
        for (int i = 0; i < N; i++) {
            wallet[i] = s.nextInt();
        }

        int index = N-1;
        int count = 0;
        while (true) {
            if(K==0) break;
            if (K < wallet[index]) {
                index = index - 1;
            }
            else {
                K = K - wallet[index];
                count = count + 1;
            }
        }
        System.out.println(count);
    }
}