정올 3431 / 백준 17619 개구리 점프(frogjump)

algorithm : sort , greedy

 

 

해설

통나무의 y좌표는 위아래로 움직일수 있기 때문에 필요 없다

 

통나무를 x1으로 정렬한다.

정렬한 통나무가 다른 통나무로 갈수 있는 지 파악해야하기 때문에 

i번째 통나무와 i + 1 통나무로 이동할수 있는지 파악한다

만약 갈수 있다면 i 번째와 i + 1는 같은 group이다.

 

출력 : 만약 같은 group 이면 1 else  0을 출력

 

#include<stdio.h>
#include<algorithm>
 
using namespace std;
 
struct data {
    int x1, x2,num=0;
    bool operator<(const data& r)
        const {
        return x1 < r.x1;
    }
};
 
struct data tree[100001];
int G_cnt[100001];
int group[100001];
int q[100001];
int N, Q;
int a, b;
int cnt;
void input() {
     
    scanf("%d %d", &N, &Q);
    for (int i = 1; i <= N; i++) {
        scanf("%d %d %d", &tree[i].x1, &tree[i].x2, &a);
        tree[i].num = i;
    }
    sort(tree + 1, tree + N + 1);
    return;
         
}
void greedy() {
     
    group[1] = 0;
    G_cnt[cnt] = tree[1].x2;
    for (int i = 2; i <= N; i++){
 
        if (tree[i].x1 <= G_cnt[cnt]) {
            if (G_cnt[cnt] < tree[i].x2)
                G_cnt[cnt] = tree[i].x2;
        }
        else G_cnt[++cnt] = tree[i].x2; 
 
        group[tree[i].num] = cnt;
    }
    return;
}
void output() {
 
    for (int i = 0; i < Q; i++) {
        scanf("%d %d", &a, &b);
        if (group[a] == group[b])
            q[i] = 1;
    }
    for (int i = 0; i < Q; i++)
    {
        if (q[i])printf("1\n");
        else printf("0\n");
    }
    return;
}
 
int main() {
    input();
    greedy();
    output();
    return 0;
}