[BAEKJOON 1449번] (C++) 수리공 항승

문제 링크

1449번: 수리공 항승

 

• 물이 처음 새는 곳의 위치에 테이프가 붙여질 것이고 좌우 0.5 만큼의 범위를 주어야 한다.
• (새롭게 테이프가 붙여진 곳 - 0.5) 부터 (새롭게 테이프가 붙여진 곳 + 테이프의 길이 - 0.5)
• 범위 내에 포함되어 있는 위치는 테이프를 통해 가릴 수 있다.
• 이 때 범위를 벗어난 곳에 물이 새는 경우 새로운 테이프를 붙이고 다시 범위를 정하여 총 필요 테이프의 개수를 정한다.

 

코드

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

using namespace std;

int N, L;
vector<float> leakPoint;

int main() {
	//input
	int tmp;
	cin >> N >> L;
	for (int i = 0; i < N; i++) {
		cin >> tmp;
		leakPoint.push_back(tmp);
	}
	
	//물이 새는 곳의 위치를 정렬
	sort(leakPoint.begin(), leakPoint.end());
	
	float range = 0;
	int answer = 0;
	//물이 새는 곳의 위치로부터 -0.5+테이프의 길이를 테이프로 가릴수있는 범위 : range 로 설정하고
	//leakPoint배열에서 range를 벗어난 경우에는 다시 그 포인트를 기준으로 range를 설정하여
	//새롭게 기준이 선정되어 새로운 테이프를 붙이게 되는 경우 answer++를 통해 총 필요한 테이프의 개수를 저장
	for (int i = 0; i < N; i++)
	{
		if (leakPoint[i]+0.5 > range){
			range = leakPoint[i] - 0.5 + L;
			answer++;
		}
	}

	//print
	cout << answer << endl;

	return 0;
}

 

결과