[dp] LIS 4 14002

LIS 4 14002

 

풀이코드

#include <iostream>
#include <vector>
 
using namespace std;
// 11053 가장 긴 증가하는 부분 수열
 
int n;
int A[1001];
 
int cache[1001];
 
int V[1001];
 
int max(int a, int b){ return a > b ? a : b; }
 
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr); 
	cout.tie(nullptr); 
	
    cin >> n;
    
    for(int i = 1; i <= n; i++){
        cin >> A[i];
    }
    
    fill_n(cache, 1001, 1);
	fill_n(V, 1001, 0);
	
 
	
	for(int i = 2; i <= n; i++){
	    for(int j = i - 1; j >= 1; j--){
	        if(A[j] < A[i]){
	            if(cache[i] < cache[j] + 1){
	                cache[i] = cache[j] + 1;
	                V[i] = j;
	            }
	        }
	    }
	}
	
	int ans = -1;
	int maxIdx = 0;
	
	for(int i = 1; i <= n; i++){
	    if(cache[i] > ans){
	        ans = cache[i];
	        maxIdx = i;
	    }
	}
	
	cout << ans << '\n';
	
	int idx = maxIdx;
	
	vector<int> vec;
	
	while(idx != 0){
	    vec.push_back(A[idx]);
	    idx = V[idx];
	}
	
	for(int i = ans - 1; i >= 0; i--) cout << vec[i] << ' ';
	
	cout << '\n';
	
	
}

 

해설

---

적용한 레시피 / 방법론 + 접근법

1

풀이

0. 이전 문제 11053 번

를 구현하고, 거기에

1. V[i] 를 추가한다.

아쉬웠던 부분 / 오답 원인 / 개선해야 할 점