[BOJ]11568 - 민균이의 계략 (C++)

문제

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

코드

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

int dp[1001];
int arr[1001];

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

    int n; 
    cin >> n; 
    for(int i=0; i<n; i++){
       cin >> arr[i];  
       dp[i]=1;
    }

    //LIS 사용
    int result = 1; 
    for(int i=0; i<n; i++){
        for(int j=0; j<i; j++){
            if(arr[i]>arr[j]){
                dp[i] = max(dp[i], dp[j] + 1); 
            }
        }
        result = max(result, dp[i]);
    }

    cout << result; 
}

풀이

이 문제는 LIS(Longest Incresing Subsequence)를 적용하면 금방 풀 수 있다.
LIS는 수열에서 가장 긴 오름차순의 부분수열의 개수를 찾아내는 알고리즘이다.
dp[]에 가장 긴 오름차순의 부분수열 크기를 저장하고 array에서 현재 보고 있는 값보다 그 뒤의 값이 더 크다면 dp의 값을 1 증가시켜준다.