그리디 알고리즘

그리디 알고리즘

현재 상태에서 최선의 선택지를 고르는 알고리즘이다.

지금까지 공부했던 알고리즘 중 개인적으로 가장 쉬웠던 알고리즘이었다!

 

문제

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

11047번: 동전 0

 

동전을 최소로 사용해서 입력된 금액을 만드는 문제이다.

예제 입력1을 보면

10 4200 // 동전 총 개수, 만들어야하는 금액
1
5
10
50
100
500
1000
5000
10000
50000

첫 번째 줄에 동전의 총 개수가 나오고, 그 다음 만들어야하는 금액이 나온다.

그 밑의 줄은 모두 동전들이다.

 

내 풀이

최소의 동전을 사용해서 금액을 만드려면 큰 값의 동전을 최대한 많이 써야한다.

큰 값 동전부터 시작해서 금액과 동전을 나눠 나온 값 만큼 동전을 쓰고, 다음 동전을 사용하는 방법으로 문제를 풀었다.

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

public class Main
{
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int num = Integer.parseInt(st.nextToken());
		int price = Integer.parseInt(st.nextToken());
		int[] coins = new int[num];
		int count = 0, gop = 0;
		
		for (int i = 0; i < num; i++) {
		    coins[i] = Integer.parseInt(br.readLine());
		}
		
		for (int i = num-1; i >= 0; i--) {
		    if (coins[i] <= price && price != 0) {
		        gop = price / coins[i];
		        price -= coins[i] * gop;
		        count += gop;
		    }
		    else if (price == 0) {
		        break;
		    }
		}
		
		bw.write(String.valueOf(count));
		bw.flush();
		br.close();
		bw.close();
	}
}