[백준] 2565번 전깃줄 (C)

문제 출처

한국정보올림피아드 지역본선 2007 초등부 4번

문제 주소

백준 2565번 전깃줄

2565번: 전깃줄

알고리즘

DP

힌트

서로 교차하지 않는 전깃줄의 최대 개수를 구한다.

문제풀이

서로 교차하지 않는 전깃줄의 최대 개수를 구하기 위해선 한 쪽 전봇대 기준으로 정렬을 한 뒤 나머지 전봇대의 번호에서 가장 긴 증가하는 수열을 구하면 된다.

#include<iostream>
#include<algorithm>
using namespace std;
typedef struct dot{
    int x,y;
}dot;

dot in[101];
int dp[101];

int cmp(dot a, dot b){
    return a.x<b.x;
}

int main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>in[i].x>>in[i].y;

    sort(in+1,in+n+1,cmp);

    int ans=0;
    for(int i=0;i<=n;i++){
        for(int j=0;j<i;j++){
            if(in[i].y>in[j].y){
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    cout<<n-ans;
}

백준 2565번 전깃줄 (C)