[ 백준 1365 ] 꼬인 전기줄 (c/c++)

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

 

 

[ 문제 요약 ]

전봇대의 개수 N이 주어지고 i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타내는 N보다 작거나 같은 자연수가 N개 주어진다. 전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지 출력한다.

 

 

[ 문제 풀이 ]

1. 꼬이게 하는 전선은 i < j 일때, A[i] > A[j]를 만족하는 수이다.

2. N - 최장 증가하는 부분 수열의 길이를 해주면 답이 된다.

3. 단순히 DP로 구하는 최장 증가하는 부분 수열의 길이는 N^2의 시간이 걸리므로 n log n에 구하는 방법을 써야한다.

4. 숫자를 입력받고 만약 수열이 비어있으면 수열에 넣는다.

5. 입력받은 숫자가 수열의 마지막 숫자보다 크면 그 뒤에 넣는다.

6. 그렇지 않다면 이분탐색을 이용하여 입력받은 수보다 작은 수 중 가장 큰 수와 바꾼다.

7. 최장 증가하는 부분 수열을 구했으니 2번에 따라 답을 출력한다.

 

 

[ 소스 코드 ]

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

int N, num, listldx = 0;
int arr[101010];

int biSearch(int low, int high, int num){
    while (low<high){
        int mid=(low + high) / 2;
        if (arr[mid] < num) low = mid + 1;
        else high = mid;
    }
    return high;
}

int main() {
    cin >> N;

    for (int i=0; i<N; i++){
        cin >> num;
        if (i==0) arr[i]=num;
        if (num > arr[listldx]) arr[++listldx] = num;
        else arr[biSearch(0, listldx, num)] = num;
    }

    cout << N - listldx - 1;
    
    return 0;
}

 

 

[ 주의할 점 ]

위 방식으로는 길이만 구할 수 있기 때문에 수열 자체를 구하기 위해서는 추가적인 작업이 필요하다.