Beakjoon 17619 개구리 점프

04 Feb 2021 in Algorithm

문제 링크 : https://www.acmicpc.net/problem/17619

나의 풀이

1. 먼저 통나무를 x1을 기준으로 정렬한다.
2. x1이 작은 통나무부터 이동이 가능한 통나무인지를 확인하여 이동이 가능하면 같은 그룹으로 묶어줌
3. 각 질문에서 주어진 두 통나무의 그룹이 같다면 이동이 가능한 경우이고, 그룹이 다르면 이동이 불가능하다는 것을 의미한다.

• 이전 그룹이 현재 통나무의 포함되기 위해서는 현재 통나무의 x1 값이 이전 그룹에서 가장 큰 x2값보다 작아야 한다. 만약 현재 통나무가 이전 그룹에 포함되었고, 현재 통나무의 x2값이 이전 그룹의 가장 큰 x2값보다 크다면 현재 통나무의 x2값을 가장 큰 x2값으로 설정한다.

풀이 코드 : 17619 개구리 점프

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

using namespace std;

struct Log{
    long long x1, x2, y;
    int idx;
};

bool compare(Log a, Log b){
    if(a.x1 == b.x1){
        return a.x2 > b.x2;
    }
    return a.x1 < b.x1;
}

int group[100001];

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    vector<Log> logs;
    int N, Q;
    Log temp;
    
    cin>>N>>Q;
    
    for(int i=0;i<N;i++){
        cin>>temp.x1>>temp.x2>>temp.y;
        temp.idx = i+1;
        logs.push_back(temp);
    }

    int start, end;
    vector<pair<int, int>> q;
    for(int i=0;i<Q;i++){
        cin>>start>>end;
        q.push_back(make_pair(start, end));
    }

    sort(logs.begin(), logs.end(), compare);

    long long last = logs[0].x2;
    int count = 0;
    group[logs[0].idx] = count;
    
    for(int i=1;i<N;i++){        
        if(last >= logs[i].x1){
            if(last < logs[i].x2) last = logs[i].x2;
        }
        else{
            last = logs[i].x2;
            count++;
        }
        group[logs[i].idx] = count; 
    }

    for(int i=0;i<Q;i++){
        if(group[q[i].first] == group[q[i].second])
            cout<<"1\n";
        else
            cout<<"0\n";
    }
}

채점결과