728x90
반응형
DP 문제이다.
순서대로 반복문을 돌다가 증가하는 부분을 확인하면서 값을 올리는 방식으로 풀면 된다.
// 가장 긴 증가하는 부분수열 4
#include <iostream>
#include <stack>
using namespace std;
int main(void){
int count, answer = 1, dp[1001], arr[1001];
stack<int> stack;
cin >> count;
for(int i = 0; i < count; i++){
cin >> arr[i];
dp[i] = 1;
for(int j = 0; j < i; j++){
if(arr[i] > arr[j] && dp[i] <= dp[j]){
dp[i] = dp[j] + 1;
answer = max(answer, dp[i]);
}
}
}
cout << answer << "\n";
for(int i = count - 1; i >= 0; i--){
if(answer == dp[i]){
stack.push(arr[i]);
answer--;
}
}
while(!stack.empty()){
cout << stack.top() << " ";
stack.pop();
}
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 제곱수의 합 (0) | 2020.11.03 |
---|---|
[algorithm] 백준 - 연속합 2 (0) | 2020.11.03 |
[algorithm] 백준 - 스티커 (0) | 2020.11.02 |
[algorithm] 백준 - 오르막수 (0) | 2020.11.02 |
[algorithm] 백준 - 쉬운 계단 수 (0) | 2020.11.02 |