[백준(Baekjoon)][자바(java)] 11047 : 동전 0 / 그리디 알고리즘

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

11047번: 동전 0

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		int cnt = 0, n = sc.nextInt(), k = sc.nextInt();
		int[] a = new int[n];
		for( int i = 0; i < n; i++ ) 
			a[i] = sc.nextInt();

		int i = n-1;
		while( k > 0 ) {
			int d = k / a[i];
			if( d > 0 ) {
				cnt += d;
				k %= a[i];
			}
			i--;
		}

		System.out.println( cnt );
		
		sc.close();	
	}
}

- 동전의 가치들을 배열에 담음

- 가장 큰 가치의 동전부터 시작 ( 최솟값을 구해야하므로 큰 것 부터 크게크게 나눠버림 )

 ( 오름차순으로 담겨있으므로 제일 끝의 인덱스부터 0까지 )

- 동전이 k원을 넘지 않으면 k원에서 동전의 가치를 나눈 값을 cnt에 추가

- 나머지는 다시 k가 됨

- k가 0이 될때까지 반복