[백준 1449번 / C++] 수리공 항승

백준의 그리디로 분류되어 있는 문제를 풀어보았다. 

 

#접근방법 

 

해당 문제는 조금만 생각해도 쉽게 풀릴 수 있다고 생각한다. 

로직은 다음과 같다. 

 

해당 지점에서 좌우 0.5 간격을 줘야한다는 말이 거창하게 들릴 수 있지만 해석해보면 

그냥 물이 새는 지점은 구멍이고 그 구멍을 막기 위해선 한 칸을 막아야한다는 뜻이다. 

 

즉, 길이가 1인 테이프를 그냥 붙이라는 말인데 말을 저렇게 하는거다. 

 

먼저 물이 새는 지점의 데이터를 받아서 오름차순으로 정렬을 한다. 

 

그 후, 시작 지점에서 바로 소유하고 있는 테이프의 길이를 더하고 -1을 해준다면 그 값이 테이프의 마지막 위치다. 

 

예를 들면, 만약 물이 새는 시작 지점이 3이고 소유하고 있는 테이프 길이가 5라면 

 

3 4 5 6 7  이라는 장소를 다 막을 수 있는 것이다. 

즉,  3(시작지점) + 5(테이프길이) -1  = 7 (end point) 

 

그래서 end point 를 갱신해 나가면서 그 값보다 큰 값을 만난 경우 다시 새로운 테이프로 붙이면서 end point를 갱신해나간다. 

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

int main() {
	int n, l, result, e; 
	cin >> n >> l; 
	vector <int> v(n); 
	for (int i = 0; i < n; i++) {
		cin >> v[i]; 
	}
	sort(v.begin(), v.end()); 
	result = e = 0; 
	for (int i = 0; i < n; i++) {
		if (e < v[i]) {
			result++; 
			e = v[i] + l - 1; 
		}
	}
	cout << result; 
}

 

1449번: 수리공 항승