[알고리즘] 동전 0(백준11047번)_실버4_반복문_조건문

문제링크

📝 문제

준규가 가지고 있는 동전은 총 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

10 4200
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 1

6

예제 입력 2

10 4790
1
5
10
50
100
500
1000
5000
10000
50000

예제 출력 2

12

---

🔍 정답

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
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());  

        ArrayList<Integer> array = new ArrayList<>();  
        for (int i = 0; i < N; i++) {  
            array.add(Integer.parseInt(br.readLine()));  
        }  
        Collections.reverse(array);  

        int cnt = 0;  
        int idx = 0;  
        while (K != 0) {  
            if (K - array.get(idx) >= 0) {  
                K = K - array.get(idx);  
                cnt++;  
            } else idx++;  
        }  
        System.out.println(cnt);  
    }  
}

• 동전의 최소 개수를 구하려면 액수가 큰 동전부터 사용해야 한다.
• 만약 K = 4,900이라면, 1,000원 4개, 500원 1개, 100원 4개가 필요하다. K에서 가장 큰 동전의 액수만큼을 빼고 더이상 뺄 수 없을 때 그 다음 동전으로 넘어가는 식으로 풀면 될 거라고 생각했다.
  • 가장 큰 동전이 1,000이라고 가정하고,
  • K에서 1,000 4개를 빼면 900원이 남는다.
  • 더이상 1,000으로 빼면 음수가 나오므로 그 다음 액수가 큰 동전으로 넘어간다. (반복)
• 따라서 ArrayList에 입력값을 넣어주고 내림차순으로 정렬한 후 K가 0이 될 때까지 위에서 이야기한 로직을 반복하고 로직이 반복되는 동안 cnt를 세어주었다!