[도전 26일차] 초고속철도 - KOI 고등부 풀이

※복습 : 

문제 : 백준 2543 초고속철도

문제 링크

 

사용 알고리즘 : Dynamic Programming

참고 :  KOI 공식 풀이

 

풀이: 기본적으로 DT 자체는 떠올리기 쉽다.

DT[i] : 1~i번째 철도까지 보았을 때의 경우의 수 

문제는 이 번째라는 것을 어떻게 정할 것인가이다.

 

이는 철도를 정렬하는 것으로 해결할 수 있다. 철도의 앞 구간을 a, 뒤 구간을 b라 하자.

 

a를 기준으로 정렬한다면 살짝 불편해지는데 a가 작고 , b가 큰 구간이 존재해서 처음부터 끝까지 DT를 채우는데 영향을 줄 수 있기 때문이다. 

b를 기준으로 정렬하면 이 점이 해결된다. 지금 보고 있는 철도 앞에 있는 철도가 나를 포함하지 못하기 때문에 편하다.

 

이제 정렬이 끝났으니 DT 간 관계식을 생각해야 한다. 

i번째 철도에 신호 발생기를 부착하느냐, 하지 않느냐로 구분한다.

 

DT 정의

1~i번째 철도를 보았을 때, 신호 발생기를 부착하는 경우의 수

신호발생기를 부착하는 경우, 경우의 수가 DT[i-1]임은 자명하다.

 

신호발생기를 부착하지 않는 경우, 1~i-1번째 철도 중에서 i번째 철도와 겹쳐 있는 구간은 모두 신호 발생기를 부착해야 한다. b(끝점)을 기준으로 정렬했으므로 'i번째 철도와 겹치지 않는 가장 번호가 큰 철도'를 찾는다면 그 철도보다 번호가 작은 철도들은 모두 i번째 철도와 겹치지 않는다 (i번째 철도와 독립적이다.)

그 철도의 번호를 id[i] 라 하자. 신호발생기를 부착하지 않는 경우는 경우의 수가 DT[id[i]]가 된다. 1~i-1번째 철도가 모두 i번째 철도와 겹치는 경우 id[i] = 0이 되고, DT[0] =1로 잡으면 된다.

 

즉,  DT[i] = DT[i-1] + DT[ id[i] ] 이다.

 

id[i]는 1~n번째 철도를 차례대로 보면서 1~i-1번째 b 집합에서 i번째 철도의 a에 대한 이진탐색을 수행하면 된다. 반대로 말하면 i번째 철도와 겹치는, 번호가 가장 작은 철도를 1~i-1중에서 찾는 것이다. 그 번호-1이 우리가 원하는 철도의 번호다. 미리 철도를 정렬해놓았으므로 이진탐색을 수행할 수 있다.

 

코드

//https://howtoliveworldnice.tistory.com/113
#include<stdio.h>
#include<algorithm>
#define N 100010
using namespace std;
int n,DT[N],id[N];
struct train{
    int a,b;
    bool operator<(const train&tmp) const{
        return b<tmp.b;
    }
}arr[N];
const int MOD = 20070713; //대회 날짜 
void input(){
    scanf("%d",&n); 
    for(int i=1;i<=n;i++)
        scanf("%d%d",&arr[i].a,&arr[i].b);
    sort(arr+1,arr+n+1);    
}
void solve(){
    int a[N]={0};
    for(int i=1;i<=n;i++){
        int x=lower_bound(a+1,a+i,arr[i].a)-a-1;
        id[i]=x; a[i]=arr[i].b;
    }
    DT[0]=1;
    for(int i=1;i<=n;i++)
        DT[i]=(DT[i-1]+DT[id[i]])%MOD;
    printf("%d",DT[n]);
}
int main(){
    input();
    solve();
} 

 

문제를 푼 후 다른 풀이를 알아보려고 구사과님의 포스팅을 보았는데 Vertex Cover이라는 개념이 등장한다. 참고하자.

 

궁금한 점이 있으시다면 질문 남겨주세요 :)

하트와 댓글은 로그인 안해도 가능해요!