[C++][백준 11053] 가장 긴 증가하는 부분 수열

[문제]

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

11053번: 가장 긴 증가하는 부분 수열

[문제 풀이]

대표적인 DP 문제중의 하나인데 접근만 잘 한다면 생각보다 쉽게 풀 수 있다.

 

가장 긴 증가하는 부분 수열을 만들기 위해서 어떤 조건이 필요한지를 생각해보자.

반복문을 통해서 계속 돌린다고 가정을 할 때

1. 현재 위치에 있는 수보다 작은 수가 지나갔던 자리에 있는가?

2. 현재 위치에 있는 수보다 작은 수 중에서 가장 큰 증가하는 길이는 몇인가?

 

 i를 1부터 n까지 돌려주자.(0자리는 무조건 1일 테니까)(14)

현재 위치의 기본값을 1로 해주자.(15)

j를 통해 현재 위치 이하를 계속 돌려주자(16)

만일 현재 위치의 수보다 이전 자리의 수가 더 작고 해당 자리에 입력시켜둔 길이가 현재 길이보다 길다면(17~18)

현재 위치의 길이를 이전 자리의 길이보다 1 더해준 값으로 만들어주자.(19)

가장 큰 값을 answer로 만들어주자.(29)

 

22~27은 필요하지 않은 코드이지만 디버깅을 할때 보기 좋기 위해 만들어뒀다.

[코드]

#include<iostream>
#include<algorithm>
#define endl "\n"
 
using namespace std;
 
int sequence[1001];
int DP[1001];
 
void solve(int n){
 
    DP[0] = 1;
    int answer = 1;
    for(int i = 1;i<n;i++){
        DP[i] = 1;
        for(int j = 0;j<i;j++){
            if(sequence[i]>sequence[j]){
                if(DP[i]<= DP[j]){
                    DP[i] = DP[j] +1;
                }
            }
            else if(sequence[i] == sequence[j]){
                DP[i] = DP[j];
            }
            else{
                continue;
            }
        }
        answer = max(answer,DP[i]);
    }
    cout<<answer<<endl;
    return;
}
 
int main(){
    int n;
    cin>>n;
    for(int i = 0;i<n;i++){
        cin>>sequence[i];
    }
    solve(n);
    return 0;
}