C++ - Greedy algorithm ( 헛간 고치기 )

그리디 알고리즘이란?

- 욕심쟁이 알고리즘, 탐욕 알고리즘으로도 알려져있다.

- 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. ( 위키 백과 )

- 각 단계에서 최선의 선택을 한 것이 전체(전역)적으로도 최선이길 바라는 알고리즘

- 각 단계에서 최선의 선택을 하기위해 정렬을 동반하는 경우가 많다.

헛간을 고쳐보자
http://220.89.64.243/30stair/barn/barn.php?pname=barn

헛간 고치기

글쓴이의 접근 방법
1. 소가 있는 우리들 사이의 간격을 구하고 내림차순으로 정렬한다. (간격 == 소가 없는 우리 -> 지붕이 필요 없는 위치)
2. 가장 낮은 번호의 소 우리 부터 가장 큰 번호 소 우리 사이를 판자 하나로 지붕을 만들 때 판자 길이를 구한다. (판자가 1개일 때의 길이)
3. 소 우리 사이 간격이 가장 큰 것부터 차례대로 사용할 수 있는 판자 개수 -1번 뺀다. (사용가능한 판자가 3개인 경우 긴 판자 1개를 2 번 자르면 3개가 되기 때문)


사용 가능한 판자 수 = 2
전체 우리 수 = 9
실제 소들이 있는 우리 수 = 5
입력 : 1,2,3,8,9

그림 1

그림 2

-구현-

#pragma warning(disable:4996)
#include <stdio.h>
#include <algorithm>
using namespace std;

int cow[220], arr[220];
int reverse(int x, int y)
{
    return x > y; // 내림차순
}
int main()
{
    int m, s, c;
    scanf("%d%d%d", &m, &s, &c);
    for (int i = 0; i < c; i++) scanf("%d", &cow[i]);

    sort(cow, cow + c); // 소 우리 오름차순 정렬

    s = cow[c - 1] - cow[0] + 1; // 판자 하나일 때 길이

    for (int i = 1; i < c; i++) arr[i - 1] = cow[i] - cow[i - 1] - 1; // 우리들 사이 간격

    sort(arr, arr + c - 1, reverse); // 간격 내림차순 정렬

    for (int i = 0; i < m - 1; i++) s -= arr[i]; // 판자 가르기

    printf("%d", s);
    return 0;
}