[백준]14002번 가장 긴 증가하는 부분 수열 4 - C/C++

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

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

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

둘째 줄에는 가장 긴 증가하는 부분 수열을 출력한다. 그러한 수열이 여러가지인 경우 아무거나 출력한다.

---

N = 1000 인 LIS 문제로 O(N^2)의 시간이 걸리는 DP를 활용한 LIS 알고리즘을 사용하여 풀 수 있는 문제이다. LIS의 배열을 구할 때 이전 원소가 몇 번째 원소인지 저장해놨다가 역추적하여 문제를 풀 수 있다.

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int N;

int arr[1000001], dp[1000001], memo[1000001],lis[1000001];
int ans=0,ans_idx=0,lis_cnt=0;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> arr[i];
	memset(dp, 0, sizeof(dp));
	memset(memo, -1, sizeof(memo));
	for (int i = 0; i < N; i++) {
		dp[i] = 1;
		for (int j = 0; j < i; j++) {
			if (arr[i] > arr[j] && dp[i] < dp[j] + 1) {
				dp[i] = dp[j] + 1;
				memo[i] = j;
			}
		}
		if (ans < dp[i]) {
			ans = dp[i];
			ans_idx = i;
		}
	}
	while (1) {
		lis[lis_cnt++] = arr[ans_idx];
		if (memo[ans_idx] == -1) break;
		ans_idx = memo[ans_idx];
	}
	cout << ans << "\n";
	for (int i = lis_cnt-1 ; i >= 0; i--) {
		cout << lis[i] << " ";
	}
	
}

  

---

사실 14003번 문제를 풀다가 시간초과가 나서 보니 N이 백만이었다. 그래서 알고리즘을 찾아보는 중 앞 번호 문제가 N 이 천으로 시간 초과가 안 날 것 같아 시간 초과 난 코드 그대로 제출하였더니 통과하였다. 저번에 알고리즘 정리를 할 때 LIS는 DP로 정리를 해놨는데 그때는 왜 이진 탐색을 활용한 O(NlogN)의 풀이를 보지 못한 지 의문이다..