#1449 수리공 항승

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

1449번: 수리공 항승

실버 3의 문제이다. 생각보다 단순한 문제였는데 너무 꼬아서 생각하느라 풀기가 힘들었다.

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

int pipe[1001];

int main()
{
  freopen("input.txt","r",stdin);
  int n,l;
  int tape=1;
  cin>>n>>l;

  if(l==1){
    cout<<n;
    return 0;
  }
  
  for(int i=0;i<n;i++)
    cin>>pipe[i];
  sort(pipe,pipe+n);

  int start=pipe[0];
  for(int i=1;i<n;i++){
    if(pipe[i]-start+1>l){
      tape++;
      start=pipe[i];
    }
  }

  cout<<tape;
}

처음에는 입력된 파이프 구멍 값을 vector에 넣고 첫번째 뺀 값과 두번째 뺀 값의 차이+1 이 L 이라면 테이프를 하나 쓰는 방식으로 코드를 구성하려 했다. 그런데 vector에서는 pop과 같은 함수가 없어서 계속 헷갈렸다. 

그리고 결정적으로 접근 방식은 비슷했으나, 첫번째 뺀 값과 두번 째 뺀 값의 차이 +1 이 L보다 크다면... 으로 코드를 구성 했어야 했다.

 

1

3

5

7

9

위와 같은 구멍이 나있다고 가정해보자.

일단 시작 지점을 첫번째 구멍인 1로 잡는다. 다음 구멍까지의 거리가 2이고 테이프로 덮으려면 +1을 해주어야한다. 따라서 1부터 3은 한 테이프로 덮을 수 있다. (테이프의 길이가 3이라고 가정 할때)

두번째 구멍에서 덮을 수 있지만 일단 세번째 구멍으로 넘어가본다. 

세번째 구멍은 거리가 5이다. 이렇게 되면 덮을 수 없고 이제 세번째 지점을 다시 시작점으로 지정하는 것이다. 그리고 테이프 개수를 담을 변수를 하나 늘려준다. 이렇게 되면 세번째 구멍 이전에 테이프를 하나 덮은 것이 됨과 동시에 시작점을 새로 잡을 수 있다.

예를들어 (1,3) 을 덮고 (3,5)를 또 덮는 과정을 생략할 수 있다는 것이다. 바로 (1,3)을 덮고 (5,7) 를 덮을 수 있다. Got it?