[JAVA] 백준 11047 - 동전0

백준 11047

문제 이해

N가지의 동전으로 K원의 돈을 구성할 때, 가장 적게 구성하는 동전 갯수를 구하면 된다.

이러한 문제는 dp방식도 있고 그리디 방식도 있다.

처음에 문제 봤을 때 효율적인 dp방식을 생각하다가 그리디로 생각을 바꾸었다.

• 동전의 가치가 오름차순으로 주어짐
• Ai는 Ai-1의 배수

두 가지 조건을 고려하면 우리가 마트에서 일반적으로 하는 것처럼 큰 동전부터 내면 된다는 것을 알 수 있다.

문제 풀이

1. 동전의 가치가 오름차순으로 주어지기 때문에 역순으로 조회하며 coin갯수와 남은 돈 계산
2. coin갯수는 몫, 남은 돈은 나머지로 계산
   
   

코드

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int K = sc.nextInt();
		
		int[] a = new int[N];
		for (int i = 0; i < N; i++) {
			a[i] = sc.nextInt();
		}
		
		int rest = K;
		int coin = 0;
		
		for (int i = N-1; i >= 0; i--) {
			coin += rest / a[i];
			rest = rest % a[i];
		}
		System.out.println(coin);

		sc.close();
	}

}