BOJ 11053 - 가장 긴 증가하는 부분 수열 (C++)

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

문제를 푼 날짜: 2024. 01. 11

#dp #lis

아이디어

$DP[i] =$ $i$번째 원소가 마지막이 되도록 추가했을 때 최대 길이

Substring vs Subsequence 헷갈리지 말기!!

• 이 문제는 Subsequence를 구하는 문제

내 풀이(C++)

#include <iostream>

using namespace std;

/*
DP + Backtracking
DP[i] : i번 쨰 원소를 추가했을 때의 최대 길이(이전까지의 원소들 중 자기보다 작은 값의 최대 DP값 + 1)
*/
int A[1010];
int DP[1010];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    int max;
    cin >> N;

    for(int i = 0; i < N; i++){
        cin >> A[i];

        max = 0;
        for(int j = 0; j < i; j++){
            if(A[j] < A[i] && DP[j] > max){
                max = DP[j];
            }
        }
        DP[i] = max + 1;
    }

    max = 0;

    for(int i = 0; i < N; i++){
        if(DP[i] > max) max = DP[i];
    }

    cout << max;
    return 0;
}