[Inflearn] 최대 선 연결하기(DP, LIS)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

오름차순으로 나열된 왼쪽 번호가 오른쪽의 같은 번호로 연결될 때,

서로 선이 겹치지 않고 선을 연결해야하는데,

우선 선이 겹치지 않으려면 왼쪽 번호도 오름차순으로 나열되어야 한다.

즉, 오른쪽 번호의 최대 증가 수열을 찾으면 되는 생각보다 간단한 문제였다.

문제에만 너무 쏠리다보면 너무 복잡하게 문제를 접근하게 되는 것 같다.

문제에서 원하는게 무엇인지를 찾아내는게 중요한데,

사실 그게 어려워서 문제를 많이 풀어봐야하는 듯 하다.

많이 풀어보자..!

+ 최대 부분 증가 수열은 다양한 문제로 만들어질 수 있다.

1. 모든 선을 다 연결한 후, 

여기서 최소 몇 개의 선을 제거하면 교차하지 않는 가장 많은 선을 남길 수 있는가.

이 문제의 경우 오른쪽 수열의 최대 부분 증가 수열을 길이를 구한 후 전체 길이(10)에서 최대 증가 수열(6)을 빼주면

결과(4)를 얻을 수 있을 것이다.

4 개의 선만 제거하면 교차하지 않는 최대 선의 개수를 구할 수 있다.

2. 다리를 만드는데 같은 번호 지점이 연결되어야 한다.

이 경우 최대 다리의 개수를 구하는 문제이다. 교차하지 않는 최대 선 연결하기와 같은 말인데

문제만 바뀐 형태이다. 

이렇게 최대 부분 증가 수열을 응용한 문제를 다양하게 만들어낼 수 있다.

#. Code

#include <cstdio>
using namespace std;
#define MAX 2147000000
#define MIN -2147000000
 
int lst[101], dp[101];
 
int main(void)
{
    int n, i, j, mx, res = MIN; 
    // freopen("input.txt", "rt", stdin);
    scanf("%d\n", &n);
 
    for (i = 1; i <= n; i++)
        scanf("%d", &lst[i]);
 
    dp[1] = 1;
    for (i = 2; i <= n; i++){
        mx = 0;
            
        for (j = i; j >= 1; j--) {
            if (lst[i] > lst[j] && mx < dp[j])
                mx = dp[j];
        }
 
        dp[i] = mx + 1;
        if (res < dp[i])
            res = dp[i];
    }
 
    printf("%d\n", res);
 
    return 0;
}

line 17) 직관적인 작은 문제의 해

line 18~29) 가장 작은 문제는 해결하였으므로 두 번째로 작은 문제부터 해를 찾아간다.

line 21~24) 기준 index 를 기점으로 전에 있는 숫자들과 비교하여
               증가수열이 되어야 하므로 해당 index의 숫자보다 크고, 거리가 가장 긴 길이를 탐색

line 26) 위 조건을 만족하는 길이에 자신을 포함한(+1) 길이를 기록 

#. Teach Code

#include<bits/stdc++.h>
using namespace std;
 
int main(){
    ios_base::sync_with_stdio(false);
    int n, res=0;
    cin>>n;
    vector<int> arr(n+1), dy(n+1);
    for(int i=1; i<=n; i++){
        cin>>arr[i];
    }
    dy[1]=1;
    for(int i=2; i<=n; i++){
        int max=0;
        for(int j=i-1; j>=1; j--){
            if(arr[j]<arr[i] && dy[j]>max){
                max=dy[j];
            }
        }
        dy[i]=max+1;
        if(dy[i]>res) res=dy[i];
    }
    cout<<res;
    return 0;
}

#. Result

  - Input --------------------------------------------------------

10

4 1 2 3 9 7 5 6 10 8

------------------------------------------------------------------

  - Output --------------------------------------------------------

6

------------------------------------------------------------------