[PS 백준 - 3.8] 1449번: 수리공 항승

문제 정보

백준 1449번 - 바로가기

• 난이도: 실버 3
• 알고리즘: 그리디 알고리즘

---

코멘트

1. 먼저 물이 새는 위치들을 벡터에 대입하고 정렬했다.
2. 첫번째 위치부터 테이프의 길이만큼 갔을 때 어느 위치까지 커버가 되는지를 찾고, 해당 범위에 포함되어 있는 구멍들을 모두 벡터에서 지웠다.

테이프에 포함되는 시작 위치와 끝 위치를 찾는 코드는 다음과 같다.

int start = *(vec.begin());
int end = start + l - 1;

---

소스 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

int main() {
	std::ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	int n, l;
	cin >> n >> l;

	vector<int> vec;

	for (int i = 0; i < n; i++) {
		int tp;
		cin >> tp;
		vec.emplace_back(tp);
	}
	sort(vec.begin(), vec.end());

	int cnt = 0;

	while (true) {

		if (vec.size() == 0) break;

		int start = *(vec.begin());
		int end = start + l - 1;
		int size = vec.size();

		while (true) {
			if (vec.size() == 0) break;
			if (vec[0] <= end) {
				vec.erase(vec.begin());
			}
			else {
				break;
			}
		}
		cnt++;
	}
	cout << cnt;
}