[백준] 11047번 – 동전 0(JAVA)

www.acmicpc.net/problem/11047

11047번: 동전 0

 

- 문제 -

---

- 풀이 과정 -

그리디 문제에서 출제되는 기본적인 형식입니다.

목표 금액을 동전의 단위가 가장 큰 값부터 나누어 주면 목표 금액을 만들기 위한 동전 개수의 최소값을 구할 수 있습니다.

 

동전의 단위를 입력 받을 배열을 선언 후 하나씩 입력 받아 배열에 저장합니다.

(배열의 역순으로 단위를 입력 받아 단위가 가장 작은 동전이 배열에 마지막에 저장되게 할 수도 있습니다.)

 

동전의 단위를 배열에 모두 저장했다면 목표 금액을 동전의 단위가 가장 큰 값부터 나누어 줍니다.

저는 단위가 가장 큰 값이 배열 마지막에 저장했기에 배열을 역순으로 사용했습니다.

 

이때 목표 금액에서 동전의 단위를 나눈 몫은 동전의 개수(count)에 저장하고

목표 금액에서 동전의 단위를 나눈 나머지는 다음 동전 단위에서 나누기 위해 저장합니다.

이런 식으로 동전의 단위가 큰 값부터 하나씩 나누어 주어 몫은 카운트하고 나머지는 다음 단위에서 나누는 값으로 사용하면 동전의 최소 개수를 구할 수 있습니다.

---

- 소스 코드 -

package com.test;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class Main { 
    //11047번 - 동전 0
    public static void main(String[] args) throws IOException {
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] str=br.readLine().split(" ");
        int n=Integer.parseInt(str[0]); //동전 개수
        int money=Integer.parseInt(str[1]); //목표 금액
        int[] coin=new int[n];
        int count=0;
        
        for(int i=0;i<n;i++) 
            coin[i]=Integer.parseInt(br.readLine()); //동전 단위
        
        for(int i=n-1;i>=0;i--) {
            count+=money/coin[i];
            money%=coin[i];         
        }
        System.out.println(count);
    }
}