백준 11047번: 동전 0 (JAVA) <그리디 알고리즘>

 

문제 해석

 

동전의 종류를 나누는 기준은 그 가치이고 준규는 동전을 총 N종류 가지고 있다.

준규가 가지고 있는 동전들을 이용해 가치의 합을 K로 만들려하고 이 때 사용하는 동전의 개수를 최소로 하고자 한다.

N과 K는 입력값으로 주어지고 동전의 가치는 둘째 줄부터 N개의 줄에 오름차순으로 주어지게 된다.

 

알고리즘

 

A1 = 1이라는 조건이 있기 때문에 K(가치 합) 은 동전을 몇개를 사용하더라도 무조건적으로 채울 수 있게 된다. 

따라서 동전을 사용해가면서 K(가치 합) 을 0으로 만들 때까지 수행하면 된다.

동전의 개수만 최소가 되면 되기 때문에 큰 가치를 가지는 동전을 우선적으로 사용함으로써 필요 개수를 최소화 시키는

그리디 알고리즘 문제이다.

 

그리디 알고리즘

 

그리디 알고리즘은 일명 탐욕 알고리즘으로 선택의 순간마다 눈앞에 보이는 최적의 상황만을 쫓아 해답에 도달하는 방식이다. 

이 문제에서는 어떤 동전을 몇개 사용해야할지 선택해야 하는 순간마다 가장 큰 가치를 가지는 동전을 최대한 사용해야

K(가치 합)을 0으로 만들 때까지 사용하는 동전의 수를 최소화할 수 있기 때문에 이 알고리즘을 사용한다.

 

코드

기본적으로 오름차순으로 정렬이 된 체로 동전의 가치를 입력해주기에 동전의 가치를 담을 배열 value를 만들고 

맨 뒤쪽 인덱스부터 순차적으로 사용해가며 사용하는 동전의 개수를 카운팅해 출력하면 된다.

이 때 동전의 가치가 남은 K보다 크면 동전을 사용할 수 없기에 적절한 조건을 달아준다.