1449 - 수리공 항승 - 그리디 알고리즘

문제

문제링크 : https://www.acmicpc.net/problem/1449

풀이전략

1. 물이 새지 않도록 테이프를 붙여서 물을 막아준다. 물을 막을때 적어도 그 위치의 좌우 0.5만큼 간격을 줘야한다는 것은 결국 구멍 하나당 테이프 길이 1이 필요하다는 말이다.
2. 테이프의 위치를 나타내는 변수를 만들어 테이프의 위치로 구멍이 커버 가능하면 그 구멍은 그냥 패스하고, 그렇지 않고 새로운 테이프가 필요하거나 좌표를 이동하여야하면 그때의 따라 조건을 바꿔준다.

코드

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;

int N, L;

int main(){

    // freopen("../input.txt","rt",stdin);
    
    scanf("%d %d",&N, &L);
    int tmp;
    vector<int> hole;
    for(int i=0; i<N; i++){
        scanf("%d",&tmp);
        hole.push_back(tmp);
    }
    // 홀을 크기에 따라 정렬하는 것은 중요하다.
    sort(hole.begin(), hole.end());
	
    // tape를 가장 첫번째 위치한 hole-1의 테이프의 길이를 더해준 것으로 한다.
    // hole을 하나 채우는데 1의 길이가 필요하므로 hole[0]-1을 해준것이고, 
    //테이프를 하나 사용해야하므로 L을 더해주었다.
    int tape = hole[0]-1 + L;
    
    int cnt = 1;
    for(int i=1; i<hole.size(); i++){
    	// hole의 위치가 tape의 위치보다 크면 새로운 tape의 위치를 할당해주고 cnt++을 해준다.
        if(hole[i] > tape){
            tape = hole[i] - 1 + L;
            cnt++;
        }
    }
    printf("%d\n",cnt);
    return 0;
}

소감

tape라는 변수를 하나 만들어 푼 것이 좋은 아이디어였다. 앞에 있는 홀부터 차례대로 테이프를 붙이면 최소한의 테이프를 사용할 수 있다는 접근을 했기때문에 이것은 그리디 알고리즘이다.