[맛있는물회] <알고리즘> 11047번 "동전 0"

우리 동비나 형님의 말을 따라 그리디알고리즘을 마스터하기 위해 백준 그리디문제를 하루에 몇문제씩 풀 생각으로 열공하고있다. ㅎㅎ

11047번은 아주 쉬운 그리디 문제이다. 

숫자도 이상하게 나와서 DP로 풀어야하는 것이 아닌 아주 전형적인 그리디알고리즘 문제!

쉽게 풀린다.!!

 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h>   int num;   int main() {     int k;     int *arr;     int cnt = 0;     int a = 0;     int i = 0;     scanf("%d %d", &num, &k);     arr = (int*)malloc(sizeof(int)*num);     for (i = 0; i < num; i++)         scanf("%d", &arr[i]);       i = num - 1;     while (1) {         if (k <= 0 || i < 0)             break;         a = k / arr[i];         if (a) {             k -= a * arr[i];             cnt += a;         }         else             i--;     }     printf("%d", cnt);     return 0; } Colored by Color Scripter

cs