백준 2565 전깃줄 - 아이디어가 중요한 DP 문제

문제 링크

www.acmicpc.net/problem/2565

풀이 아이디어

아이디어가 되게재밌다.

우선 전기줄이 '겹치게 되는는' 조건이 어떻게 되는지를 한번 생각해 봐야된다.

왼쪽 전봇대에서 위 아래로 시작하는 줄이 오른쪽 전봇대에서 아래 위로 끝나면 겹치게 된다.

근데 이렇게 생각하기 시작하면 개인적으로 좀 어려워 진다고 생각한다.

 

하나 기준을 정해야 한다. 왼쪽 전봇대로 정하는 것이 편하다. sort가 편하기 때문이다.

그러면 왼쪽 기준으로 정렬 되어있는 상태에서 for문을 돌릴 때, 

오른쪽 에서 대소관계의 순서가 유지되면 안겹치는 것이다.

문제의 그림을 예시로 들자면 A를 기준으로 오름차순 정렬을 한 후 탐색을 진행하는 것이다.

1,2에서 시작하는 전기줄은 각각 8,2에서 끝난다.

1,2를 볼 필요도 없이 8,2 만 보고도 아 대소관계가 바뀌었으니 얘네 둘은 겹치네 

라고 판단을 할 수 있다는 것이다.

그말인 즉슨 정렬 후 B만 보고도 답을 구할 수 있다는 것이다.

A를 오름차순 정렬 후 B의 해당되는 숫자들을 나열하면 [8,2,9,1,4,6,7,10] 이다.

이 [8,2,9,1,4,6,7,10] 중 가장 긴 부분 수열의 길이를 구하는 것이 

가장 전깃줄이 안겹치면서 유지할 수 있는 최대한의 전깃줄 수를 구하는 것이다.

즉 [8,2,9,1,4,6,7,10] 을 구하는 것으로 문제가 바뀌는 것이다..

 

어디서 많이 본 문제 아닌가? 바로 dp의 대표문제 가장 긴 증가하는 부분수열이다.

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

 

sort만 잘 할 수 있게 저장만 잘 해두면 나머지는 어렵지 않게 풀 수 있을 것이다.

 

코드

#include <bits/stdc++.h>
using namespace std;

int n;
int dp[101];

int main(void){
    cin>>n;
    int s,e;
    vector<vector<int>> v;
    for(int i=0; i<n; i++){
        cin>>s>>e;
        v.push_back({s,e});
    }
    sort(v.begin(),v.end());
    int ans=0;
    for(int i=0; i<n; i++){
        dp[i]=1;
        for(int j=0; j<i; j++){
            if(dp[j]+1>dp[i] && v[i][1]>v[j][1]){
                dp[i]=dp[j]+1;
            }
        }
        ans = max(ans,dp[i]);
    }
    cout<<n-ans;
}