그리디 알고리즘을 적용하는 첫 번째 문제입니다.
오름차순으로 입력된 동전의 가치를 위에서부터 차례대로 사용합니다.
동전을 사용하면서 매번 조합해야 하는 금액을 넘지 않는지 체크를 해주어야 합니다. 기본적으로 입력의 조건을 보면, 다음 원소는 이전 원소의 배수라는 조건이 있습니다. 여기를 확인해보시면 동전 교환에서는 탐욕 알고리즘으로 최적해를 구하지 못하는 경우의 수가 있지만, 문제 자체에서 배수 조건을 줌으로써 문제 형태를 매트 로이드로 만들었습니다.
따라서 알고리즘만 구현하면 풀 수 있는 쉬운 문제입니다.
핵심 알고리즘은 다음과 같습니다.
|
1
2
3
4
5
6
7
8
|
//동전의 가치가 가장 큰 것부터 비교를 시작합니다.
for(int i=N-1; i>=0; i--) {
//몫 연산자가 0보다 커야 그 동전을 사용할 수 있음 -> 만들고자 하는 K가 4000인데 10000을 사용할 수 있나?
//몫 연산자의 결과가 적어도 1은 나와야 함 if((K/money[i])>0) {
count += K/money[i];
K = K%money[i];//다음 연산에서는 동전을 사용하고 남은 돈에 대헤 가치를 생각해야 한다.
}
}
|
cs |
조합하고자 하는 K를 최소 개수의 동전으로 구성하려면 당연히 가치가 큰 것부터 채워주어야 합니다. 따라서 동전의 종류를 오름차순으로 저장한 money배열을 가장 마지막 원소부터 차례대로 검색을 해줍니다.
K를 동전의 가치로 몫 연산자를 진행했을 때, 적어도 1 이상의 값은 나와야 해당 동전을 사용할 수 있다는 의미입니다. 몫 연산자의 결과가 0이라면 조합하고자 하는 수보다 동전의 가치가 더 크기 때문에 적절하지 않음을 알 수 있죠.
나누기 결과의 "몫"이 사용한 동전의 개수가 됩니다. 그만큼 count변수에 추가해주시고, 반드시 동전을 채우고 남은 금액을 나머지 연산자로 갱신해주어야 합니다.
'알고리즘 > 백준[문제풀이]' 카테고리의 다른 글
| 자료구조[queue]_백준_11866 (0) | 2022.04.27 |
|---|---|
| 알고리즘[Greedy]_백준_1931 (0) | 2022.04.24 |
| 자료구조[큐]_백준_5430 (0) | 2022.04.24 |
| 자료구조[스택]_백준_4949 (0) | 2022.04.21 |
| 스택_10773_제로 (0) | 2022.04.20 |
