[백준] 2565, 2568 전깃줄 1, 2

전깃줄 문제를 처음 접했을 때 앞에 가장 긴 시리즈 문제들을 해결을 한 상태라서 되게 쉽게 느껴졌다.

 

그림을 본 순간 든 생각은 A와 연결된 B애들을 순서대로 적어보자! 였다.

적자마자 수열이 떠올랐다. ㅋㅋ

 

해당 수열을 가지고 가장 긴 증가하는 수열을 찾고 전체 길이에서 빼주면 답이 나온다. ㅎㅎ

 

가장 긴 시리즈에서 유용하게 사용했던 Dp + 이진탐색을 활용해서 문제를 해결했다.

 

전깃줄 2

길이를 구하는 건 쉬운데 또 부분 수열의 요소들을 찾으랜다.

이것 역시 가장 긴 수열 시리즈에서 했던 역추적 방법을 사용하면 풀 수 있다.

 

역추적을 하고 나면 위에서 작성했던 가장 긴 부분 수열은 {1, 4, 6, 7, 10}이 나오게 된다.

그러면 {8, 2, 9, 1, 4, 6, 7, 10}에서 가장 긴 부분 수열의 요소들을 못 찾는 경우 해당 요소를 출력해 주면 된다.

간단하죠?

 

□ 소스 코드

void electronic2568(){
    int n;
    scanf("%d",&n);
    
    vector<int> lis;
    vector<pair<int, int>> array(n);
    vector<int> backTrace;
    
    for(int i=0;i<n;i++)
        scanf("%d%d",&array[i].first,&array[i].second);
    
    sort(array.begin(),array.end());
    
    lis.push_back(array[0].second);
    for(int i=0;i<array.size();i++){
        if(lis.back() < array[i].second){
            lis.push_back(array[i].second);
            backTrace.push_back(lis.size() - 1);
        }
        else{
            long index = lower_bound(lis.begin(), lis.end(), array[i].second) - lis.begin();
            lis[index] = array[i].second;
            backTrace.push_back(index);
        }
    }
    
    printf("%d\n",n-lis.size());
    
    vector<int> result;
    int temp = lis.size() - 1;
    for(int i= backTrace.size() - 1; i>=0; i--){
        if(temp == backTrace[i]){
            temp--;
            result.push_back(array[i].first);
        }
    }
    
    for(int i=0;i<array.size();i++)
        if(find(result.begin(),result.end(),array[i].first) == result.end())
            printf("%d\n",array[i].first);   
}

 

□ 유용한 반례

/*
 4
 1 2
 2 3
 3 4
 4 1
 
 ANS: 1
 Sequence: 4
 */