BOJ 14002 가장 긴 증가하는 부분 수열 4

1 개요

BOJ 14002 가장 긴 증가하는 부분 수열 4

• 백준 온라인 저지 14002번 문제
• BOJ 34단계

2 같이 보기

• BOJ 11053 가장 긴 증가하는 부분 수열
• BOJ 11054 가장 긴 바이토닉 부분 수열
• BOJ 11055 가장 큰 증가하는 부분 수열
• BOJ 11722 가장 긴 감소하는 부분 수열
• BOJ 12015 가장 긴 증가하는 부분 수열 2
• BOJ 12738 가장 긴 증가하는 부분 수열 3
• BOJ 14003 가장 긴 증가하는 부분 수열 5

3 C++

#include <bits/stdc++.h>
using namespace std;

int N;
int A[1001];
int dp[1001];
int visited[1001];

void solve() {
    int max = 0;
    int maxIdx = 0;
    for (int i=1; i<=N; i++) {
        dp[i] = 1;
		for (int j=1; j<i; j++) {
			if (A[i] > A[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
				visited[i] = j;
			}
		}
		if(dp[i] > max) {
		    max = dp[i];
		    maxIdx = i;
		}
	}
	stack<int> s;
    for(int i=maxIdx; i>0; i=visited[i]) {
        s.push(A[i]);
    }
	cout << max << '\n';
	while(!s.empty()) {
	    cout << s.top() << ' ';
	    s.pop();
	}
}

int main() {
    cin >> N;
    for(int i=1; i<=N; i++) {
        cin >> A[i];
    }
    solve();
}