[백준,BOJ 11047] 동전 0(JAVA 구현)

- 풀이

  이전에 풀었던 문제였지만, 블로그에 글을 게시하지 않았던 문제이다. 단계별 풀어보기의 그리디 알고리즘으로 분류되어 있는 첫 번째 문제이다. 그리디 알고리즘이란, 한 상황에서 취할 수 있는 최대 이득을 취하는 알고리즘이라 한다. 이러한 방식은 이전 분류인 동적 프로그래밍의 과정이 너무 많은 연산이 이루어지기 때문에 이를 보완하기 위해 고안된 알고리즘이라 한다. 한 상황에서 최선의 것을 선택하다 보니 최적의 해를 보장하지 않는다는 특징이 있다고 한다.

 

  그리디 알고리즘으로 분류되어 있는 특징처럼 문제에서 주어진 값 k를 최소한의 동전 개수로 이루기 위해서는 가장 높은 단위의 화폐부터 사용하면 최소한의 동전 개수를 사용하게 된다. 최소한의 동전 개수를 이루기 위해 가장 높은 단위의 화폐부터 사용한다는 점에서 최선의 선택인 그리디 알고리즘이라 할 수 있다고 생각한다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		
		// 동전의 종류 
		int n = in.nextInt();
		
		// 만들어야 하는 가치의 합
		int k = in.nextInt();
		
		int cnt =  0;
		
		// 동전들의 가치
		int a[] = new int[n];
		
		for(int i=0;i<n;i++) {
			a[i] = in.nextInt();
		}
		
		// 가장 높은 가치의 동전부터 탐색
		for(int i=n-1;i>=0;i--) {
			// 해당 가치가 k보다 작을 경우,
			if(a[i]<=k) {
				// 나눈 값이 해당 동전의 개수가 되고
				cnt += k/a[i];
				// 나머지를 다시 k로 대입하면 된다.
				k %= a[i];
			}
		}
		
		System.out.println(cnt);
		
		in.close();
	}

}