[백준.11047-C언어] 동전 0

문제. 

동전을 적절히 사용해서 그 가치의 합을 K로 만들려고 한다. 이때 필요한 동전 개수의 최솟값을 구하는 프로그램을 작성하시오.

 

입출력.

첫째 줄에 N과 K가 주어진다. (1 ≤ N ≤ 10, 1 ≤ K ≤ 100,000,000) 둘째 줄부터 N개의 줄에 동전의 가치가 오름차순으로 주어진다. (1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수)

첫째 줄에 K원을 만드는데 필요한 동전 개수의 최솟값을 출력한다.

 

방법.

k의 값이 동전의 가치보다 작으면 해당 동전은 사용할 수 없다.

그렇기 때문에 k의 값이 동전보다 크거나 같은 동전만을 사용할 수 있다. ( k > 동전의 값 )

(예) k=4000, 동전=5000 → 동전은 사용할 수 없다. / k=4000, 동전 3000 → 동전을 사용할 수 있다.

 

동전을 최소로 사용해야하니 사용할 수 있는 동전 중 가장 큰 값을 k에서 빼고, 결과적으로 k가 0이 될 때까지 이 과정을 반복한다. 그리고 사용한 횟수를 결과적으로 출력해야하므로 cnt라는 변수에 동전 사용 횟수를 저장해 출력했다.

#include <stdio.h>

int main(void){     

    //백준 11047
    int n, k;
    scanf("%d %d", &n, &k);
    int arr[n];
    
    //입력
    for(int i=0; i<n; i++){
      scanf("%d", &arr[i]);
    }
    
    //k가 0이 아니라면 반복
    int cnt=0, idx=n-1;
    while(k!=0){
        if(k>=arr[idx]){
            k-=arr[idx];
            cnt++;
        }else{
            idx--;
        }
    }

    //출력
    printf("%d",cnt);
    
    return 0; 
}

 

Insight.

처음에 코드를 짤 때에는 사용할 수 있는 동전의 가장 큰 값을 구하기 위해 계속해서 for문을 사용해 k의 값과 비교하도록했는데 계속 시간초과되더라. 음 사실 k의 값은 0을 향해 계속 감소하니까 한번이라도 k보다 큰 가치를 가진 동전으로 판별되었다면, 사용될리가 없으니 매번 for문을 사용해 모든 동전과 k의 값을 비교하는건 비효율적이라.. 정답은 출력되긴 했지면 시간초과가 나왔다.

 

그리고 백준에서 키워드로 그리디 알고리즘을 제시하고 있어서 한 번 찾아보고 정리해봐야겠다.

 

 

 

 

11047번: 동전 0