BOJ 13334 철로

www.acmicpc.net/problem/13334

13334번: 철로

 

이 문제를 단순화 시킨다면 다음과 같이 정의할 수 있다.

"시작점으로부터  거리 d (d > 0) 보다 가까이 있는 도착점의 개수 중 최대 값" 

 

그래서 시작점, 도착점을 각각 벡터에 저장하여 정렬한 뒤, 2-pointer를 사용하여 문제를 해결하였다.

시작점으로부터 거리가 d 초과인 도착점이 나올 때 까지 도착점의 index를 하나씩 늘렸고, 그에 따라 local_answer도 1씩 늘렸다 

거리가 d 초과인 도착점이 나오면, 시작점의 index를 늘리고 local_answer을 1 줄였다. 

그리고 local_answer이 지금까지 구한 값 중에 최대 값인지 확인하고 최대 값이면 answer 에 저장하였다.

코드는 다음과 같다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n,d,s,e;
int input[100000][2];
vector<int> start;
vector<int> last;
int answer = 0;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&(input[i][0]),&(input[i][1]));
        if(input[i][0] > input[i][1]) swap(input[i][0],input[i][1]);
        start.push_back(input[i][0]);
        last.push_back(input[i][1]);
    }
    scanf("%d",&d);


    sort(start.begin(), start.end());
    sort(last.begin(), last.end());
    
    s =0, e=0;
    int local_answer = 0;
    while(true){
        while(e < last.size() && last[e] - start[s]<=d ){
        	//printf("%d %d : %d\n",s, e, start[s]-last[e]);
            ++e;
            ++local_answer;
        }
        if(local_answer > answer) answer = local_answer;
        if(e == last.size()) break;
        ++s;
        --local_answer;
        if(s == start.size()) break;
    }
    

    printf("%d\n",answer);
    return 0;
}

 

 

그런데 계속 틀렸다고 떠서,  며칠을 고민했다.

내가 계속 오답을 받았던 이유는, 집-사무실의 거리가 d 초과인 쌍에 대해 제거 처리를 하지 않았기 때문이었다.

예제는 통과했지만, 예제를 살짝 수정하면, 정답이 나오지 않는다.

반례는 다음과 같다.

8
5 35
35 25
10 20
10 25
30 50
50 60
30 25
80 100
30

 

 

이를 수정하였고, 코드는 다음과 같다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int n,d,s,e;
int input[100000][2];
vector<int> start;
vector<int> last;
int answer = 0;
int main(){
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d%d",&(input[i][0]),&(input[i][1]));
        if(input[i][0] > input[i][1]) swap(input[i][0],input[i][1]);
    }
    scanf("%d",&d);
    for(int i=0;i<n;i++){
        if(input[i][1] - input[i][0] > d) continue;
        start.push_back(input[i][0]);
        last.push_back(input[i][1]);
    }


    sort(start.begin(), start.end());
    sort(last.begin(), last.end());
    
    s =0, e=0;
    int local_answer = 0;
    while(true){
        while(e < last.size() && last[e] - start[s]<=d ){
        	//printf("%d %d : %d\n",s, e, start[s]-last[e]);
            ++e;
            ++local_answer;
        }
        if(local_answer > answer) answer = local_answer;
        if(e == last.size()) break;
        ++s;
        --local_answer;
        if(s == start.size()) break;
    }
    

    printf("%d\n",answer);
    return 0;
}