11047)동전 0

https://www.acmicpc.net/problem/11047

문제를 풀어도 개운치가 않아서 다른 풀이를 찾아봤다.

어떻게 하면 이런 생각을 할 수 있을지 의문이 들면서

내가 솔루션을 찾는 방식을 되돌아 볼 필요성을 느꼈다.

4790원이 주어진다. 10종류의 동전을 최소한으로 사용해 4790원을 만들 때 사용된 동전 갯수를 찾아야 한다.

1.동전 배열에서 K = 4200원을 만들기 위한 가장 큰 동전을 찾는다.(1000원)

2.그 동전으로 K = 420790을 나눈 몫을 합산한다.(동전의 갯수 저장)

3.그 동전으로 나눈 나머지로 K를 갱신한다. (K = 200)

4.1000원보다 작은 동전이 되게끔 인덱스를 하나 감소시킨다.

K를 나타낼 수 있는 최대 크기의 동전을 찾으면 나머지 돈들은 그 이하의 동전들로 표현할 수 있다.

1000원보다 작은 동전은 500원인데 500원으로 200을 나눈 몫은 0이고 나머지는 200이다.

그래서 최대 크기의 동전을 찾고난 후 동전 크기를 차례대로 줄여가며 위 과정을 반복해도

문제를 해결하는데 지장이 없다.

#include<stdio.h>
 
int main() {
    int N, K;
    int *coin;
    int count = 0;
    int tempIndex = 0;
 
    scanf("%d %d", &N, &K);
    coin = (int *)malloc(sizeof(int)*N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &coin[i]);
    }
 
    for (int i = 0; i < N; i++) {
        if (coin[i] <= K) {
            tempIndex = i;
        }
    }
 
    while (K > 0) {
        count += K / coin[tempIndex];
        K = K % coin[tempIndex];
        tempIndex--;
    }
    printf("%d\n", count);
 
    return 0;
}