백준 24229 모두싸인 출근길

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

24229번: 모두싸인 출근길

스위핑을 통해 푸는 문제였습니다.

 

문제에서 제시한 두번째 예시와 마찬가지로 주의할점은 점프할 수 있는 판자는 한가지가 아니라는 점입니다. 따라서 완전탐색으로 점프 하는 경우의수를 모두 체크할경우 경우의수가 매우 커지게됩니다.

 

문제에서 요구하는 것은 갈 수 있는 최대 좌표를 구하는 것입니다. 만약 겹치는 판자를 모두 합쳐 각 판자가 점프로 갈 수 있는 최대 좌표를 고정하게된다면 한번의 탐색으로 갈 수 있는 최대좌표를 구할 수 있습니다. 이를 위해 전처리를 하려면 판자의 시작점을 오름차순으로 정렬하고 시작점이 같을경우 끝점을 내림차순으로 정렬하여 겹치는 판자를 합쳐야 합니다.

전처리가 끝난후 각 판자에서 점프를 통해 갈 수 있는 최대 좌표를 구해가며 판자의 시작점과 비교하여 탐색하면 됩니다.

 

#include<stdio.h>
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
class plane{
public:
int s,e;
plane(int start,int end){
    s=start;
    e=end;
}
bool operator < (const plane & p2){
    if(this->s == p2.s){
        return this->e>p2.e;
    }
    else return this->s<p2.s;
}
};
int main(){
    int N;
    cin>>N;
    vector<plane> vec;
    vector<plane> vec2;
    int start=0;
    int end=0;
    for(int x=0;x<N;x++){
        int s,e;
        cin>>s>>e;
        vec.push_back(plane(s,e));
    }
    sort(vec.begin(),vec.end());
    for(auto i : vec){
        if(start==0 && end==0){
            start=i.s;
            end=i.e;
        }
        if(end>=i.s){
            end=max(end,i.e);
            start=min(i.s,start);
        }
        else{
            vec2.push_back(plane(start,end));
            start=i.s;
            end=i.e;
        }
    }
    vec2.push_back(plane(start,end));
    int solve=0;
    int cango=0;
    for(int x=0;x<vec2.size();x++){
        if(vec2[x].s>cango){
            break;
        }
        else{
            cango=max(cango,vec2[x].e*2-vec2[x].s);
        }
        solve=max(solve,vec2[x].e);
    }
    cout<<solve<<'\n';
}