[ 그리디알고리즘 ] 11047 백준 동전0 - 자바 Java

출처 : https://www.acmicpc.net/problem/11047

문제

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

z1 5 10 50 100 500 1000 5000 10000 50000

예제 출력 2

12

---

돈과 거스름돈의 종류가 주어졌을 때 필요한 거스름돈의 개수를 구하는 문제입니다.  

 

11047 백준 동전0 자바 코드

import java.io.IOException;
import java.util.Scanner;

public class coin0 {

     public static void main(String[] args) throws IOException {
		
        Scanner sc = new Scanner(System.in);
        
        int num = sc.nextInt();		//입력개수 추출
        int price = sc.nextInt();	//값 추출
		
        int arr[] = new int[num];		
        int cnt=0;
		
        for(int i=0;i<num;i++) {
          arr[i] = sc.nextInt(); //입력개수만큼 입력한 값을 배열에 넣습니다.			
        }
		
        for(int i=num-1; 0<=i;i--) {
           if(arr[i]<=price) {
              cnt += price/arr[i]; //몫을 세면 문제에서 요구하는 개수를 구할 수 있습니다.				
              price %=arr[i];      //나머지값으로 다음 구할 값을 구합니다.						
           }
        }
		
        System.out.println(cnt);		
		
    }	
}

 

정리

1. 입력값을 얻습니다.
2. 값(금액)을 얻습니다.
3. 입력개수 만큼 입력한 값을 배열에 넣습니다.
4. price(금액)/arri [i](입력개수)을 하여 cnt(거스돈의 개수)를 구합니다.
5. 나머지값으로 다음 구할 값을 구합니다.

여기서 중요한점은

거스름돈의 개수는 돈을 나누었을 때, 몫이 바로 거스름돈의 개수입니다.

 

감사합니다.