[BOJ] 11047 동전 0

#include <stdio.h>

int coin[10];

int main(void)
{
    int i, n, k, div;
    int result = 0;

    scanf("%d %d", &n, &k);
    for (i = 0; i < n; i++)
        scanf("%d", &coin[i]);
    for (i = 1; i < n; i++) {
        div = (k % coin[i]) / coin[i - 1];
        result += div;
        k -= coin[i - 1] * div;
    }
    result += k / coin[n - 1];
    printf("%d", result);

    return 0;
}

풀이: 15분
코딩: 6분
개선: 17분

인접한 동전이 배수관계임에 힌트를 얻었다.
크기가 작은 동전들로 큰 동전을 대체할 수 있으며 큰 동전으로 표현할 수 없다면 반드시 작은 동전으로 채워야한다.
두 종류의 동전만 있는 경우, 큰 동전으로 먼저 채우면 남은 값이 작은 동전으로 나누어 떨어진다.
이 방법을 모든 동전에 대해 반복하여 값을 얻었다.
위의 두 번째 반복문으로는 동전이 한 가지인 경우와 가장 큰 동전의 개수를 고려할 수 없다.
처음엔 각각을 따로 처리했는데 전자는 가장 큰 동전 하나만 있는 것과 마찬가지로 반복문 바로 아래의 한 문장으로 둘을 모두 처리할 수 있음을 깨달았다.
또한 2차원 배열로 각 동전의 개수를 저장했다. 그러나 다른 사람이 작성한 코드를 보며 반복문 안에서 사용할 변수 하나만 있으면 1차원 배열로 충분하다는 것을 알고 수정했다.