그리디(Greedy) 알고리즘

참조 : https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

설명 : 탐욕이라는 이름에 걸맞게 상황마다 최선의 선택을 했을 때가 결국 전체적으로 최선의 결과가 나오는 알고리즘이다.

• 선행조건 2가지
  • 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  • 최적 부분 구조 : 문제에 대한 최선의 선택이 전체적으로 최선의 선택이어야 한다.
• 동적 계획법의 열화판이다.

푼 문제 :
https://www.acmicpc.net/problem/11047
https://www.acmicpc.net/problem/1931

11047 동전 0
푼 시간 : 10분 이내

해설 : 그리디 시리즈의 첫 문제였다. 동적 계획법에서 고생을 하다와서 그런가 별로 어렵지 않았다. 그리디 알고리즘 자체도 동적 계획법의 열화판이었다. 마음 편하게 매 순간마다 최선의 선택을 해서 그 값을 한 변수에 저장해서 풀었다.

중간에 조건 설정을 잘못해주어서 헤멨지만 금방 해결했다. (같을 때)

#include <stdio.h>
#include <malloc.h>
int count = 0;

int count_coin(int coin_value, int *k)
{
    int multiply_coin = 0;
    while (*k >= coin_value)
    {
        *k -= coin_value;
        multiply_coin++;
    }
    return (multiply_coin);
}

int main()
{
    int n, k;
    scanf("%d %d", &n, &k);
    int *coin_value = malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        scanf("%d", &coin_value[i]);
    for (int i = n - 1; i > -1; i--)
    {
        if (coin_value[i] <= k)
            count += count_coin(coin_value[i], &k);
    }
    printf("%d", count);
    free(coin_value);
}