[11047번] 동전 0 (Greedy Algorithm)

문제 출처 : 

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

알고리즘 분석 :

최적의 값을 찾아내는 과정이니 결국 Greedy Algorithm(탐욕 알고리즘)이 녹아있는 문제이다.

하지만 이 문제에 다음과 같은 조건이 없었다면 Greedy Algorithm으로 접근 해서는 안된다.

(1 ≤ Ai ≤ 1,000,000, A1 = 1, i ≥ 2인 경우에 Ai는 Ai-1의 배수) 이 조건이 있기에 탐욕 알고리즘을 이용 할 수 있다.

탐욕 알고리즘의 문제중 쉬운 문제에 해당하므로 소스 코드를 이용하여 문제를 해석하자.

소스 코드 : 

#include <stdio.h>
 
int main()
{
    int n, money;
    int i;
    int arr[11];
    int cnt = 0;
 
    scanf("%d %d", &n, &money);
 
    for (i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }
 
    for (i = n - 1; i >= 0; i--)
    {
        if (money - arr[i] >= 0)
        {
            money = money - arr[i];
            cnt++;
            i++;
        }
        
    }
 
    printf("%d", cnt);
    return 0;
}
 
//                                                        This source code Copyright is Crocus 
//                                             Do you want to see more contents? click here >>