[백준OJ] 1449번 수리공 항승

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

1449번: 수리공 항승

---

 

 

-풀이-

먼저, 입력된 물이 새는 곳의 위치를 오름차순을 해준다.

처음 테이프를 붙이는 곳의 위치를 arr[0]으로 해준뒤, 정렬된 배열을 탐색하면서, 테이프를 붙인곳과의 거리가 L보다 작다면, 테이프를 새로 붙일 필요가 없으므로 넘어가고, L보다 크거나 같다면 새로운 테이프를 추가해서 붙이고, 테이프의 시작점을 갱신해주면 된다.

이때 L보다 크거나 같아야 하는 이유는, 문제에서 주어진 좌우 0.5만큼의 간격을 줘야한다는 조건때문이다.

 

예를들어 1 , 2 , 3 위치에서 물이 새는중이고, 테이프의 길이가 2라고 한다면, 1,2,3 모두 한 테이프로 묶을 수 없다. 왜냐하면 1에 붙일때, 테이프의 끝이 1이 아닌, 0.5부터 붙여야 하기때문에 0.5~2.5까지 테이프가 커버를 하기때문에 3을 가릴 수 없다. 따라서 2.5부터 다시 테이프를 붙여야해서 2개가 필요하게 되는것이다. 이런 이유때문에 조건문을 조심해서 제출해야한다.

 

-시간복잡도-

N개의 배열을 한번만 탐색하면 되므로 O(N)이 되지만, 정렬을 할때, O(NlogN)이 걸리므로, 최종적으론 O(NlogN)이 된다.

 

-코드-

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

int arr[1001];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int n, l;
	cin >> n >> l;

	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}

	sort(arr, arr + n);

	int st = arr[0];
	int cnt = 1;
	for (int i = 1; i < n; i++) {
		if (arr[i] - st >= l) {
			st = arr[i];
			cnt++;
		}
	}
	cout << cnt;
}