[BaekJoon/백준] 11047번 [ 그리디 알고리즘 ]

배수관계로 내림차순으로되어있으니 그리디알고리즘을 사용할 수 있다.

 

각 단계마다 해당 값보다 크지 않은 수 중 가장 큰 수를 최적값으로 선택해주면 된다.

 

동전으로

A1 A2 A3가 오름차순으로 차례로 주어졌다고 봤을 때

A3 = A2 x X 라고 볼 수 있다. 배수이기 때문에.

 

이러한 특성 덕에 각 단계에서 해당 값보다 크지 않은 최적의 수를 선택해주면 된다.

 

 

 

만약 배수관계가 아닌 경우, 800원의 가치값에 100 400 500원이 주어진다면, 이는 그리디알고리즘으로 풀 수 없다.

500원 x 1 + 100원 x 3 = 4개

400원 x 2 = 2개 이기 때문이다.

 

문제에서는 각 수가 배수관계이기 때문에, 가치값보다 A3가 작다면, A3를 사용하는게 A2를 여러번 사용하는 것 보다 최적일 수 밖에 없다.

 

이런 특징 덕에 그리디 알고리즘을 사용할 수 있는 것.

 

ex) 100 500 1000 5000 이고, 가치값이 4000이라면

500은 100의 배수, 1000은 500의 배수이기에

100원짜리를 40번 사용하는 것 보다 500원짜리를 8번 사용하는게 낫고, 이보다는 1000원짜리를 4번 사용하는게 낫다. 5000은 가치값보다 크므로 사용할 수 없다.

 

 

코드

#include <stdio.h>

int coin[10];
int N;
int K;
int C = 0;
int x;

int main() {
    scanf("%d %d", &N, &K);
    
    for(int i = 0; i < N; i++) {
        scanf("%d", &coin[i]);
        
        if(coin[i] <= K) // for문이 끝나면, 가치값보다 크지 않으면서 그 중 가장 큰 수의 인덱스가 x에 담긴다.
            x = i;
    }
    
    
    for(int i = x; i >= 0; i--) {
        if(coin[i] <= K) {
            C += K / coin[i];
            K %= coin[i];
        }
    }
    
    printf("%d", C);
}