C++ / 백준 / 1449 / 수리공 항승

문제

 

https://www.acmicpc.net/problem/1449

1449번: 수리공 항승

 

 

문제풀이

 

테이프를 자르거나 겹쳐서 붙이는 것은 굳이 생각 안 해도 된다.

물을 막을 때, 그 위치의 좌우 0.5만큼 간격을 주면 1만큼의 테이프가 필요 없다고 생각하면 된다.

따라서 입력받은 테이프의 길이를 1 빼준다.

 

그다음 정렬을 해서 왼쪽부터 테이프를 붙인다.

테이프를 붙이게 되면 위치를 저장해 놓고 다음 구멍에 갔을 때, 이미 테이프가 붙여져 있는지 확인을 한다.

안 붙여져 있으면 붙이고 위치를 새로 기록해 놓는다.

 

코드

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

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), L(0);
	cin >> N >> L;

	--L;

	vector<int>location(N, 0);
	for (int idx = 0; idx < N; ++idx) {
		cin >> location[idx];
	}
	sort(location.begin(), location.end());

	int prev(-1000), answer(0);
	
	for (int idx = 0; idx < N; ++idx) {
		if (location[idx] > prev + L) {			
			++answer;
			prev = location[idx];
		}
	}
	cout << answer;
}