백준(S2) 11047번: 동전 0 (C언어 C11 C99)

코드를 보기 전에: 이 문제는 그리디 알고리즘이다.

동전 문제는 그리디 알고리즘의 정말 단골 문제다.

나는 동전 문제를 풀때마다 입력된 값에서 큰 동전부터 빼도록 한다.

 

Fullcode

 

#include <stdio.h>
int coin[10];
int main()
{
    int n, k;
    int cnt = 0;
    scanf("%d %d", &n, &k);
    for (int a = 0; a < n; a++)
    {
        scanf("%d", &coin[a]);
    }
    int a = n - 1; // 배열이므로 입력한 값에서 1을 빼야한다.
    while (k > 0) // k가 0이 되면 끝나므로 굳이 break문을 만들필요가 없어졌다.
    {
        if (coin[a] > k) // 배열 값이 입력한 값보다 크면 다음 배열로 넘어가게 만들었다.
            a--;
        else
        {
            k -= coin[a]; // 입력한 값이 더 크면 배열 값을 빼도록 했다.
            cnt++;
        }
    }
    printf("%d", cnt);
}