🍞 Problem Solving/Baekjoon

[백준] 1449 수리공 항승 c++

박빵이 2022. 9. 2. 00:45
 

1449번: 수리공 항승

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나

www.acmicpc.net

 

풀이과정

일단 위치 입력 받은 것을 sort함수로 정렬해준다.  
물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야한다고 했으니 loc[i] - start에 1씩 더해준다. 

그 값이 테이프의 길이보다 더 클 경우 개수를 카운트해주며 시작지점(start)을 loc[i]로 업데이트해준다.

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

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

	int N, L, loc[1001];
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> loc[i];
	}
	sort(loc, loc + N);

	int start = loc[0], res = 1;
	for (int i = 1; i < N; i++) {
		if (loc[i] - start + 1 > L) {
			res++;
			start = loc[i];
		}
	}
	cout << res;
}