백준 11047 동전0

Algorithm/백준

백준 11047 동전0

chbong 2022. 8. 13. 00:40

문제

준규가 가지고 있는 동전은 총 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원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

package ch.baekjoon;

/*
백준 11047
동전 0
 */

import java.util.Scanner;

public class Algorithm9 {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String first = sc.nextLine();
        String[] temp = first.split(" ");
        int len = Integer.parseInt(temp[0]);
        int price = Integer.parseInt(temp[1]);
        int result = 0;
        int chk = 0;
        int[] arr = new int[len];
        for(int i = 0; i < len ; i++) {
            arr[i] = sc.nextInt();
        }

        for(int i = len-1; i >= 0; i-- ){

            result += price / arr[i];
            chk = price / arr[i];
         price -= arr[i] * chk;
        if(price == 0 || price < 0) break;



        }

        System.out.println(result);



    }
}

풀이

첫째 줄에 동전의 개수와 돈을 받아서 split 으로 공백을 쪼개어 나눈다.

string 으로 받은것이기 때문에 int로 형변환 해준 뒤 , 가격과 길이를 나눈다.

각각의 화폐 크기만큼을 arr 배열에 담은 후 큰 화폐부터 금액을 나누면서 몫만큼을 더해간 뒤,

가격에서 더한 금액을 빼준다.

금액이 0 원이되면 break하고 출력하여 해결