[BOJ][C++] 백준 1365번: 꼬인 전깃줄

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

 

문제

공화국에 있는 유스타운 시에서는 길을 사이에 두고 전봇대가 아래와 같이 두 줄로 늘어서 있다. 그리고 길 왼편과 길 오른편의 전봇대는 하나의 전선으로 연결되어 있다. 어떤 전봇대도 두 개 이상의 다른 전봇대와 연결되어 있지는 않다.

문제는 이 두 전봇대 사이에 있는 전깃줄이 매우 꼬여 있다는 점이다. 꼬여있는 전깃줄은 화재를 유발할 가능성이 있기 때문에 유스타운 시의 시장 임한수는 전격적으로 이 문제를 해결하기로 했다.

임한수는 꼬여 있는 전깃줄 중 몇 개를 적절히 잘라 내어 이 문제를 해결하기로 했다. 하지만 이미 설치해 놓은 전선이 아깝기 때문에 잘라내는 전선을 최소로 하여 꼬여 있는 전선이 하나도 없게 만들려고 한다.

유스타운 시의 시장 임한수를 도와 잘라내야 할 전선의 최소 개수를 구하는 프로그램을 작성하시오.

입력

첫 줄에 전봇대의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N보다 작거나 같은 자연수가 N개 주어진다. i번째 줄에 입력되는 자연수는 길 왼쪽에 i번째 전봇대와 연결된 길 오른편의 전봇대가 몇 번 전봇대인지를 나타낸다.

출력

전선이 꼬이지 않으려면 최소 몇 개의 전선을 잘라내야 하는 지를 첫째 줄에 출력한다.

 

풀이

그림으로 생각하면 조금 어렵지만 풀이법만 생각해내면 의외로 간단하다

 

이 문제의 목표를 보자

: 최소한의 전선을 잘라내서 "꼬이지 않은 상태의 전선들"만 남겨둬야한다.

 

전선이 꼬이지 않으려면 어떻게 해야할까?

반대로 생각해보자, 전선이 꼬이는 경우는 어떤 경우일까?

한 전봇대가 '자신의 앞에 있는 전봇대가 연결된 전봇대'의 앞쪽 전봇대와 연결되면 그 순간 전선은 꼬이게 된다.

왼쪽 길에 있는 전봇대를 기준으로, n번째 전봇대는 n-1번째 전봇대가 연결된 오른쪽 전봇대보다 뒤쪽에 연결되어야한다.

 

설명이 길었으나 결론은 간단하다.

가장 긴 증가하는 부분 수열을 구하면 된다. (= 최장 부분 증가 수열, = Longest Increasing Subsequent)

그리고 해당 수열에 들어가지 않는 전선들은 다 끊어버리자

 

최장 부분 증가 수열을 구하는 과정에서는 dp를 사용한다

보통 dp[i] : v[i]로 끝나는 최장증가부분수열 <- 이렇게 하는데, 이 경우 이중 for문으로 인해 시간초과가 뜬다

이분탐색을 이용해서 dp[i] : 길이 i의 가장 긴 증가하는 부분 수열 중 가능한 가장 작은 마지막 값 으로 구해보자

 

코드

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int getLowerBound(int target, vector<int>&v) {
    int left=0, right=v.size();
    while(left<right) {
        int mid = (right-left)/2 + left;
        if(v[mid] < target) {
            left = mid+1;
        } else {
            right = mid;
        }
    }
    return left;
}

int main() {
    // 입력
    int n;
    cin >> n;
    vector<int>v(n);
    for(int i=0; i<n; i++) {
        cin >> v[i];
    }
    
    // 풀이
    vector<int>dp;
    dp.push_back(v[0]);
    for(int i=1; i<n; i++) {
        if(dp.back() < v[i]) {
            dp.push_back(v[i]);
        } else {
            int idx = getLowerBound(v[i], dp);
            dp[idx] = v[i];
        }
    }
    int lis = dp.size();
    
    // 출력
    cout << n - lis;
    
    return 0;
}

 

 

시행착오 

dp를 이용하여 최장 증가 부분 수열을 구했으나 시간초과가 떴다.

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 입력
    int n;
    cin >> n;
    vector<int>v(n);
    for(int i=0; i<n; i++) {
        cin >> v[i];
    }
    
    // 풀이
    vector<int>dp(n,0); // dp[i] : v[i]로 끝나는 최장증가부분수열
    dp[0] = 1;
    for(int i=1; i<n; i++) {
        int tmpMax = 0;
        for(int j=0; j<i; j++) {
            if(v[j]<v[i] && tmpMax<dp[j]) {
                tmpMax = dp[j];
            }
        }
        dp[i] = 1+tmpMax;
    }
    
    // longest increasing subsequent
    int lis = *max_element(dp.begin(), dp.end());
    
    // 출력
    cout << n - lis;
	
    
    return 0;
}