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

 

어려웠다.

 

어떻게 접근해야 할지 고민하다가 알아낸 것이, 전깃줄이 교차되는 경우의 수였다.

예제의 1부터 10까지의 전봇대를 생각해볼 때, 1부터 10까지를 배열의 index처럼 취급할 수 있을 것이다.

만약 이 index가 더 후위에 있다면, 이 인덱스에 해당하는 배열의 값도 더 후위에 있어야 한다.

즉 1이 3으로 연결되어 있다면 2부터 10까지는 적어도 4 이상과 연결되어 있어야 1과 교차하지 않는다.

 

그러나 문제가 생기는 것이 바로 0이었다.

만약 1이 0이라고 한다면 2 ~ 10까지는 1이상과 연결되어도 되는 것이니 아무런 문제가 없다.

 

그러나 만약 index 2가 0이라고 한다면, 사실 index 2는 값과 무관하게 항상 앞전과 교차할 일이 없어야 하겠지만,

컴퓨터는 이 0을 0이라는 전봇대와 연결한 것으로 인식해서 항상 교차한다는 결론을 내린다.

그래서 일단 각 전봇대에서 교차되지 않고 이어질 수 있는 최장 값을 구하되, (dp : dynamic programming)

 

모든 것이 끝난 다음에 배열의 값이 0이었던 경우에는,

index가 더 작은 모든 범위에 대하여 최대 값보다 +1 만큼을 지니게 하고,

배열의 값이 0이 아닌 경우에는

index가 더 작은 모든 범위에 대하여 값이 0인 경우의 개수를 더 해준다.

 

이렇게 해서 모든 dp를 수정해준 다음에, 수정된 dp 중 최대값을,

전체 전봇대의 개수에서 빼주면 제거해야 할 전봇대의 개수가 나오게 된다.

 

코드를 보면 더 이해하기 쉬울 것이다.

그리고 이걸 배우면서 LIS (longest increasing sussequence), 최장 증가 수열이라는 것을 알게 되었다.

나는 이걸 모르고 경우의 수를 따져 가면서 했지만,

 

어떠한 수열에서, 값이 오름차순으로 증가할 수 있는 최장 길이를 구하는 방식을 의미하는데,

이 전봇대도 전봇대를 무시하고 배열 그 자체로만 보게 될 경우 최장 길이를 구하라는 방식에,

"0" 이라는 함정을 숨겨놓은 문제였다.

 

#include <iostream>
using namespace std;
 
int n, maxV;
int arr[501];
 
int main(void)
{
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int from, to;
        cin >> from >> to;
 
        arr[from] = to;
        if (maxV < from) maxV = from;
    }
 
    int dp[501];
    for (int i = 1; i <= maxV; i++)
        dp[i] = 1;
 
    int remove = 0;
    for (int i = 1; i <= maxV; i++)
    {
        for (int j = 1; j < i; j++)
        {
            if (dp[j] + 1 > dp[i] && arr[j] < arr[i] && arr[j] != 0) dp[i] = dp[j] + 1;
        }
    }
 
    for (int i = 1; i <= maxV; i++)
    {
        if (arr[i] == 0)
            for (int j = 1; j < i; j++)
            {
                if (dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
            }
        else
            for (int j = 1; j < i; j++)
            {
                if (arr[j] == 0) dp[i]++;
            }
 
        if (dp[i] > remove) remove = dp[i];
    }
 
    cout << maxV - remove;
}
 
// 1 1 2 1 0(1) 2 3 0(1) 4 5
// 1 1 2 1 3    3 4 5    6 7
 
// 위의 값들은 dp[]의 값들이다.
// 밑의 값은 마지막에 0을 고려해서 다시 구해준 dp 값이다.
// 0(1) 이라고 표시되있는 것은, 배열의 값이 0이라 dp[]값은 1인 경우를 의미한다.

 

풀다가 좌절도 많이 했고, 매우 오랜 시간이 걸렸다.