백준 11053. 가장 긴 증가하는 부분 수열 [C++]

문제 : 가장 긴 증가하는 부분 수열

유형 : 동적 계획법

문제 해석

• 유명한 LIS 알고리즘이다.

• 원소가 n 개인 배열의 일부 원소를 골라내서 만든 부분 수열 중, 각 원소가 이전 원소보다 크다는 조건을 만족하고, 그 길이가 최대인 부분 수열을 최장 증가 부분 수열이라고 한다.

• LIS 알고리즘은 시간 복잡도가 O(N2)과 O(NlogN) 2가지 방법이 있다.

해결 전략

• 시간 제한이 1초이고, N의 크기가 최대 1000이므로 시간 복잡도가 O(N2)인 방법으로 풀 수 있다.

설계, 구현

• LIS의 길이는 최소 1이므로 모두 1로 초기화 시킨다.

• i 번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이는 i번째 값이 가지고 있는 LIS 길이와 [0, i)구간에서 이미 저장돼 있는 LIS 길이 + 1를 비교하여 큰 값이, i 번째 값이 가지는 가장 긴 증가하는 부분 수열의 길이이다.

코드

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

int N;
int A[1001];
int DP[1001];

void init() {
	cin >> N;
	for(int i = 0; i < N; i++) {
		cin >> A[i];
		DP[i] = 1;
	}	
}

void solve() {
	int answer = 0;
	
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < i; j++) {
			if(A[i] > A[j]) {
				DP[i] = max(DP[i], DP[j] + 1);
			}
		}
		answer = max(answer, DP[i]);
	}
	
	cout << answer;
}

int main() {
	init();
	solve();
	
	return 0;
}

피드백

동적계획법은 글로 정리하는 게 어렵다. 😂
설계, 구현 부분을 어떻게 써야 할지 꽤 오래 생각했다.