백준 11047. 동전

🅰 백준 11047. 동전

11047번: 동전 0

 

✏️ 문제 풀이

• 동전 문제가 그리디로 성립하기 위해서는 주어진 동전이 배수의 조건을 맞아야 한다. 

 

• 가장 큰 동전의 가치부터 동전의 개수만큼 가격에서 / 를 해서 나오는 값이 필요한 동전의 개수이므로 계속 더해준다.
• needCoin = 필요한 동전의 개수
• pay[] = 동전 종류의 가격

✏️ 소스코드

package greedy;

import java.util.*;
import java.io.*;

public class Main_실버2_11047_손은성 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		int pay[] = new int[N];
		int needCoin = 0;
		// N만큼 금액 확인
		for (int i = 0; i < N; i++) {
			pay[i] = Integer.parseInt(br.readLine());
		}

		// 필요 동전개수 구하기
		for (int i = N - 1; i >= 0; i--) {
			needCoin += K / pay[i];
			K = K % pay[i];
		}
		System.out.println(needCoin);
	}
}

 

✅ 후기

• 그리디 알고리즘의 제일 기초적인 문제이다. 가격이 제일 높은 동전부터 거스름돈을 걸러주면 쉽게 풀 수 있다.