(C++) - 백준(BOJ) 1449번 : 수리공 항승 답

www.acmicpc.net/problem/1449

1449번: 수리공 항승

greedy문제였습니다.

 

풀이방법

 1. 물이 세는 위치를 저장할 배열을 선언하고 입력받습니다. 오름차순 입력 보장이 안되므로 입력 후에는 오름차순으로 정렬해줍니다.

 2. 테이프가 칠해지지 않은 곳을 발견하면 그 위치부터 + l까지 1000을 안넘는 공간에 한해 테이프를 붙입니다. 그 후 테이프의 개수를 저장하는 변수 ans를 1더해 줍니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int leakPoint[1001];
int taped[1001];
int n, l, ans;
int main(){
    cin >> n >> l;  
    for(int i = 0; i < n; i++) cin >> leakPoint[i];
    sort(leakPoint,leakPoint+n);
    for(int i = 0; i < n; i++){
        if(!taped[leakPoint[i]]){
            for(int j = leakPoint[i]; j < min(leakPoint[i] + l, 1001); j++) taped[j] = 1;
            ans++;
        }
    }
    cout << ans <<'\n';
}