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

---

https://www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

 

DP문제이다.

for문 하나로 어떻게 풀지? 끙끙대다가 포기하고 LIS 알고리즘에 대해 검색해보았다.

 

최장 증가 부분 수열(LIS, Longest Increasing Subsequence)

: 일부 원소를 골라내어 만든 부분 수열 중, 각 원소가 전 원소보다 크고(증가), 그 길이가 최대인 부분 수열

 

크게 O(n^2)로 푸는 방법, O(nlogn)으로 푸는 방법 2가지로 나뉘어있었다.

이 문제는 전자로 해도 무리가 없었기 때문에(사실 내가 어려워서) 이중 for문을 사용하였다.

 

그림 설명

입력을 받는 배열 A,

동적 프로그래밍을 이용하는 배열 DP

총 2개의 배열을 만들어주었다.

 

예시를 보면 이해가 갈 것이다!

 

전체 코드는 아래와 같다.

#include <iostream>
using namespace std;

int A[1001]; int N;
int DP[1001] = { 0,1, }; 
// DP[i] : i번째 수를 마지막 원소로 가지는 LIS의 길이
int maximum;
int ans = 1; // 정답은 최소 1

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> N;

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

	for (int i = 2; i <= N; i++) {
		maximum = 0;
		for (int j = 1; j < i; j++) { // 최댓값 찾기
			if (A[j] < A[i] && DP[j] > maximum) {
				// 현재 A[i]값보다 작으면서, LIS 길이가 제일 큰 것
				maximum = DP[j]; // maximum에 담음
			}
		}
		DP[i] = maximum + 1; // DP[i]는 maximum으로부터 길이가 1 추가된 것임
		ans = (DP[i] > ans) ? DP[i] : ans; // DP[N]이 최댓값이 아니므로 바로 비교해서 정답에 넣음
	}
	cout << ans;
}