백준 11053번 - 가장 긴 증가하는 부분 수열

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

LIS 문제로 굉장히 유명한 문제이다.
처음에 알고리즘 수업을 들었을 때 이해하기 힘들었던 기억이...
그리고 개인적으로 정답률 38%에 비해 더 어려운 문제처럼 느껴진다. 

어렵다기보다는 좀 까다로운 부분과 예외처리에서 이해가 안되는 부분이 있다고 느꼈다.


우선 두 가지 방법으로 문제를 해결할 수 있도록 하였다.
첫 번째는 dp를 이용하여 이중 for문을 이용해 해결하는 방식이다.

#1

첫 번째 접근 방법부터 생가해보면

예를들어 위에 나와있는 예시에서 첫 번째 원소인 10과 두 번째 원소인 20의 각각의 증가하는 부분 수열의 길이는 1과 2이다. 

그리고 4번째 원소 까지 그 값을 구했다고 가정해보자.

이때 5번째의 증가하는 부분 수열의 길이 값은 

첫 번째 원소부터 4번째 원소까지 반복문을 실행하여 각각의 원소를 5번째 원소의 값과 비교하여 구한 값이다. 

만약 5번째 원소의 값이 크고 증가하는 부분수열의 값이 더 크다면 5번째 원소의 증가하는 부분 수열의 값은 

비교하는 인덱스의 증가하는 부분수열의 값보다 1이 더 크게 된다.



처음 반복문을 돌 때 각각의 증가하는 부분 수열의 값인 dp값을 1로 초기화해서 이를 실행하면 된다.

주의해야할 점은 주석으로 표시를 했는데 
이전 원소 인덱스를 before라고 하고 현재 구하려는 인덱스를 current라고 할때
dp[before] <  dp[current] +1의 조건을 만족 해야 한다.


그 이유는 10,20,10,30이 있을 때
세 번째 까지 구한 dp 값은 두 번째 까지 구한 dp값에 +1을 해서 길이가 3이된다.
그러나 dp[before] < dp[current]만을 비교하게 되면, 세 번째 길이가 2가 된다.
즉 마지막 원소에서 증가하는 부분 수열의 원소를 추가해주어야 하기 때문에 +1로 비교를 해야한다.


개인적으로 헷갈리는 부분은모든 dp값을 0으로 지정한 다음에 첫 번째 원소의 dp값만 1로 지정해서 이를 실행해도 문제가 없다고 생각했다. 

반례를 생각해도 떠오르지가 않아서 좀 더 고민을 해봐야겠다.

#include <iostream>
#include <algorithm>
using namespace std;
 
int main(){
    
    int n,length=1;
    cin>>n;
    
    int A[1000]={0};
    int dp[1000]={0};
    
    for(int i=0;i<n;i++)
        scanf("%d",&A[i]);
    
    dp[0]=1;
 
    for(int i=1;i<n;i++){
        
        dp[i]=1; //각 자리의 숫자 길이를 1로
        
        for(int j=0;j<i;j++){
            if(A[i]>A[j] && dp[i]<dp[j]+1){ //비교할 때 dp[j]+1로
                dp[i]=dp[j]+1;
            }
        }
        length=max(length,dp[i]);
    }
 
    
    cout<<length<<endl;
    return 0;
}

#2

두 번째 접근 방법은 
location이라는 증가하는 부분 수열의 공간을 새로 만들어서 여기다가 증가하는 부분 수열을차례대로 구하는 방법이다. 

그리고 추가가 될때마다 length값을 더해줘서 길이를 구하는 방식이다.


이 방법이 좋다고 생각하는 이유는 증가하는 부분 수열의 길이 뿐만 아니라 해당 길이에 따른 수열의 원소도 같이 구할 수 있기 때문이다.
(물론 위의 방법에서 역순으로 출력할 수 있지만 한번 더 반복 작업을 해줘야 한다.)

값을 비교할 때
location의 마지막 원소, 즉 이제까지 구한 증가하는 부분 수열의 마지막 원소와 현재 비교하려는 수열 A의 값을 비교하는 것이 포인트다.

만약 A의 값이 더 크다면 location의 마지막에 A의 원소를 추가해줘서 길이가 늘어나게 된다.


만약에 그렇지 않다면
location의 첫 번째 원소부터 비교를 시작해서 수열 A의 값이 작거나 같은 경우가 있을 때,
그 자리에 수열 A의 값을 넣어주면 된다.



예를들면
10,20,30, 5,10,15,20이 있다고 가정해보자.

10,20,30까지 location에 삽입되어 있고 5부터 다시 비교를 한다면
5,20,30이 된다.

그리고 10을 비교를 해서 
5,10,30이 된다.

그리고 15를 비교를 해서
5,10,15가 된다.

마지막으로 20을 비교를 해서
5,10,15,20이 된다.


이렇게 원소를 다시 삽입해주는 이유는 맨처음에 증가하는 부분 수열의 길이가 6이 있었어도
뒤에서부터 다시 시작하는 길이가 7인, 증가하는 부분 수열이 있다면 이를 반영해줘야 하기 때문이다.

#include <iostream>
using namespace std;
 
int main(){
    
    int n,length=0;
    cin>>n;
    
    int A[1000]={0};
    int location[1000]={0};
    
    for(int i=0;i<n;i++)
        scanf("%d",&A[i]);
    
    location[0]=A[0];
    
    for(int i=1;i<n;i++){
        
        if(A[i]>location[length])
            location[++length]=A[i];
        else{
            for(int j=0;j<=length;j++){
                if(A[i]<=location[j]){
                    location[j]=A[i];
                    break;
                }
            }
        }
    }
    
    cout<<length+1<<endl;
    return 0;
}