Q1 동전 0(11047번 문제)

728x90

📌 문제

문제)
동전 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

📌 문제 분석❗️

첫째 줄에서 동전의 개수 N과 가치 합 K를 받는다. 입력 값을 확인해보면 알 수 있듯이 오름차순으로 정렬되어있다. 따라서 별도의 정렬 코드는 구현하지 않아도 된다. 구하고자 하는 값은 결국 동전의 개수를 최소로 조합하여 가치 합 K를 만드는 것이다.

그림을 그려보자면...

선택 1을 진행한 뒤 선택 2를 하고자할 때 전, 후는 서로에게 영향이 전혀 없다. 따라서 해당 문제는 그리디 알고리즘을 통해 최선의 선택(가장 큰 동전을 선택)으로 최소의 동전 개수를 뽑아내면 된다.

📌 선언한 변수

변수 종류	변수 명	설명
BufferedReader	br	입력 값을 받기 위한 버퍼 함수 선언
StringTokenizer	st	받은 입력 값을 공백 기준으로 N(동전 종류)과 K(가치 합)으로 분리
int	coin	받은 동전을 내림차순으로 조건에 따라 동전 값을 누적하여 가치 합 K와 비교하기 위해 선언
int	ans	소모된 동전을 카운트하기 위해 선언
int[]	coinList	입력받은 동전을 저장하기 위해 선언, 크기는 N(동전 개수)만큼 할당

📌 진행

❗️for문을 감소식 형태로(내림차순으로 저장할 수 있게) coinList 배열에 값을 저장한다.

        // 이미 오름차순으로 정렬되있으므로 따로 정렬해주지 않는다.
        for (int i = N - 1; i > -1; i--) {
            coinList[i] = Integer.parseInt(br.readLine());
        }

❗️forEach(Enhanced for)문을 사용해 큰 동전부터 값을 비교한다.

        for (int x : coinList) {
            if (x <= K) {
                while (coin + x <= K) {
                    ans ++;
                    coin += x;
                }
            }
        }

x(뽑아낸 동전)가 K(가치합)보다 작거나 같을 경우 if문을 실행해준다.
while(coin + x <= K)
→ 동전을 소모해봤을 때 K보다 크지 않을 때까지
ans ++;
coin += x;
→ coin에 동전 값을 누적하고 ans(소모된 동전 수)를 증감시켜준다.
ans 값을 출력

📌 전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

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 coin = 0;
        int ans = 0;
        int[] coinList = new int[N];

        // 이미 오름차순으로 정렬되있으므로 따로 정렬해주지 않는다.
        for (int i = N - 1; i > -1; i--) {
            coinList[i] = Integer.parseInt(br.readLine());
        }
        // 출력용(디버깅)
//        System.out.println(Arrays.toString(coinList));

        for (int x : coinList) {
            if (x <= K) {
                while (coin + x <= K) {
                    ans ++;
                    coin += x;
                }
            }
        }

        System.out.println(ans);
        br.close();
    }
}