[dp] 11053 LIS 가장 긴 증가하는 부분 수열

11053 LIS 가장 긴 증가하는 부분 수열

 

풀이코드

#include <iostream>

using namespace std;
// 11053 가장 긴 증가하는 부분 수열

int n;
int A[1001];

int cache[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);
	
	int ans = -1;
	
	for(int i = 2; i <= n; i++){
	    for(int j = i - 1; j >= 1; j--){
	        if(A[j] < A[i]){
	            cache[i] = max(cache[i], cache[j] + 1);
	        }
	    }
	}
	
	for(int i = 1; i <= n; i++){
	    ans = max(ans, cache[i]);
	}
	
	cout << ans << '\n';
	
}

 

해설

---

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

풀이

1. N 이 1000이 최대이기 때문에 브루트 포스는 불가하다.

2. D[i] : A[1] 부터 A[i] 있다고 하고, A[i] 를 마지막으로 하는 LIS 의 길이를 저장한다.3. D[i] = max(D[j]) + 1 (j < i, A[j] < A[i] 를 만족하는 j)

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

1. 무분별한 헤더 파일 사용을 자제하자. 필요할 때 꺼내쓸 수 있도록

2. 이전에 풀었던 방식 과 비교하였을 때 확연히 깔끔한 코드라고 볼 수 있다. 필요한 것만, 간결한 코드 작성에 힘쓰자.