#11047 : 동전 0

풀이방법

사용된 것:

그리디 알고리즘

 

2022.01.24

가지고 있는 동전을 액수가 큰 것부터 차례대로 살핀다.

현재 살피는 중인 동전의 액수 값을 t라 한다.

만들어내야 하는 금액을 k라 한다.

출력할 답은 ans에 저장한다. ans의 초기값은 0이다.

만약 t<k라면

(t/k)를 ans에 더하고, k의 값을 (t%k)로 변경한다.

가장 작은 액수의 동전을 살필 때까지 이 과정을 반복한다.

ans를 출력한다.

 

코드

Java(2022.01.24)

import java.util.Scanner;

public class Main {

	public static void main(String[] args){
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int n = sc.nextInt();
		int k = sc.nextInt();
		int[] coins = new int[n];
		int t;
		int ans = 0;
		
		for(int i = n-1; i>=0; i--) {
			coins[i] = sc.nextInt();
		}
				
		for(int i = 0; i<n; i++) {
			t = coins[i];
			if (t<= k) {
				ans += k/t;
				k = k%t;
			}
		}
		
		System.out.print(ans);
		
		sc.close();
	}

}