코드업 2634:거스름돈 II(C)

문제 설명

여러분은 실력을 인정받아 전 세계적으로 사용할 수 있는 자동판매기용 프로그램의 개발을 의뢰받았다.

이번에도 역시 자동판매기에서 이용자에게 거스름돈을 남겨줄 때, 거스름돈에 사용될 동전의 수를 가정 적게하는 것이다.

입력으로 거슬러 줘야할 돈의 액수와 그 나라에서 이용하는 동전의 가지 수 그리고 동전의 종류가 들어온다.

여러분은 그 돈의 액수를 거슬러 주는 여러가지 방법들 중 가장 적은 동전은 몇개인지 구하는 프로그램을 작성해야 된다.

 

입력

첫 번째 줄에는 거슬러 줘야할 돈의 액수가 입력된다. (이 값은 10,000원 이하이다.)

다음 줄에는 그 나라에서 사용되는 동전의 종류의 수가 입력된다. (단 동전의 수는 10이하이다.)

마지막 줄에는 동전의 수 만큼의 동전 액수가 오름 차순으로 입력된다. (동전의 최대값은 10,000원 이하이다.)

모든 입력에 대해 답이 있음을 보장한다.

 

출력

최소의 동전의 수를 출력한다.

 

입력 예시

730

5

10 50 100 500 1250

 

출력 예시

6

 

나의 코드

#include <stdio.h>

int main()
{
    int m, n, i, j;
    scanf("%d%d", &m, &n);	// 거스름돈, 동전 갯수 입력
    int count[m + 1], num[n];	// 배열 선언
    count[0] = 0;
    for (i=0;i<n;i++)	// 돈 입력
        scanf("%d", &num[i]);

    for (i=1;i<=m;i++)
    {
        count[i] = m + 1;	// 카운트 값 설정
        for (j=0;j<n;j++)
        	// 비교하면서 최솟값 구함
            if (num[j] <= i)
                count[i] = (count[i] < count[i - num[j]] + 1) ? count[i] : count[i - num[j]] + 1;
    }

    printf("%d", count[m]);	// 값 출력

    return 0;
}

 

문제 바로가기:https://codeup.kr/problem.php?id=2634&rid=0