[백준(BOJ)] 11047번: 동전 0 (Greedy Algorithm(그리디 알고리즘), C++)

📝 문제풀이 과정

---

최소의 동전 개수가 되려면 가장 큰 동전부터 사용해야 한다.

따라서 배열 A 끝에서부터 탐색을 하고, A[i] > K이면 continue한다. 그렇지 않으면 count에 K / A[i], 즉 A[i]에서 최대로 사용할 수 있는 동전 개수를 더하고, 그만큼 K % A[i]를 K를 줘서 이미 할당한 것은 제외했다.

 

 

💻 C++ 제출코드

---

#include <stdio.h>
using namespace std;

int main(){
    int N,K, count=0; // N: 동전의 종류, K: 가치의 합
    scanf("%d %d", &N, &K);
    int A[N];

    for(int i=0; i<N; i++) scanf("%d", &A[i]);

    for(int i=N-1; i>=0; i--){
        if(A[i] > K) continue;
        count += K / A[i];
        K %= A[i];
    }
    printf("%d\n", count);
}

 

 

👏 결과

---