문제
항승이는 품질이 심각하게 나쁜 수도 파이프 회사의 수리공이다. 항승이는 세준 지하철 공사에서 물이 샌다는 소식을 듣고 수리를 하러 갔다.
파이프에서 물이 새는 곳은 신기하게도 가장 왼쪽에서 정수만큼 떨어진 거리만 물이 샌다.
항승이는 길이가 L인 테이프를 무한개 가지고 있다.
항승이는 테이프를 이용해서 물을 막으려고 한다. 항승이는 항상 물을 막을 때, 적어도 그 위치의 좌우 0.5만큼 간격을 줘야 물이 다시는 안 샌다고 생각한다.
물이 새는 곳의 위치와, 항승이가 가지고 있는 테이프의 길이 L이 주어졌을 때, 항승이가 필요한 테이프의 최소 개수를 구하는 프로그램을 작성하시오. 테이프를 자를 수 없고, 테이프를 겹쳐서 붙이는 것도 가능하다.
입력
첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나 같은 자연수이다.
출력
첫째 줄에 항승이가 필요한 테이프의 개수를 출력한다.
정답코드
#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'
using namespace std;
int main()
{
FASTio;
int n,l;
cin >> n >> l;
vector<int> v(n,0);
for(int i=0; i<n; i++)
cin >> v[i];
sort(v.begin(),v.end());
int start=v[0], cnt=1;
for(int i=1; i<n; i++)
{
if(v[i]-start<l) continue;
cnt++;
start = v[i];
}
cout << cnt << endl;
return 0;
}
풀이 및 사고과정
문제를 이해하는데 조금 시간이 걸렸던 것 같다.
근데 문제를 이해하고 나서는 "회의실 배정" 문제와 같은 느낌이나서 어떻게 하면 테이프를 최소 갯수로 쓸 수 있을까 생각해보고 코드를 짰다.
근데 채점1%에서 바로 틀려서 뭐지하고 의아해했다. 아무리 반례를 찾아보아도 다 정답이었다.
알고보니 오름차순으로 위치가 입력되는 게 아니라서 정렬하는 과정이 필요했다. TC만보고 오름차순으로 입력이 주어질 줄 알았지만 따로 언급이 안돼있어서 모르는 일이었다. 문제에서 주어진 규칙을 객관적으로 바라볼 필요가 있을 거 같다.
