[백준/BOJ] 11053번 가장 긴 증가하는 부분 수열 (C++)

www.acmicpc.net/problem/11053

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

DP 유형의 문제로, LIS(Longest Increasing Subsequence)의 개념을 알게된 문제였습니다.

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dp[1001];

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    int n, answer = 0;
	cin>>n;
	vector<int> v(n + 1);
	
	for(int i = 1; i <= n; i++) {
		cin>>v[i];
	}
	
    // dp 배열을 1로 초기화
	fill(dp + 1, dp + 1001, 1);
	
    // LIS(Longest Increasing Subsequence) : 최장 증가 수열
    // 2번부터 n번까지 각각 최대 증가하는 수열의 길이가 저장된다. 
	for(int i = 2; i <= n; i++) {
		for(int j = 1; j <= i; j++) {
            if(v[i] > v[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
	}
	
	for(int i = 1; i <= n; i++) {
		answer = max(answer, dp[i]);
	}
	
	cout<<answer;
}