BOJ - 14002번, 가장 긴 증가하는 부분 수열 4 문제, LIS 예제와 DP 풀이

이번에는 거의 1년을 묵혀놨다가 다시 한번 14002번 문제를 푼 과정을 정리해보려 합니다.

21년 2월 22일에 풀었다가 결국에 틀린 문제

문제는 LIS(Longgest Increasing Subsequence) 문제 즉, 가장 긴 증가하는 부분 수열 문제 중 하나로 dp를 사용해서 쉽게 풀이할 수 있었습니다.

 

사실 지금에서야 쉬워진거지, 작년에는 생각나는 방법을 총 동원해도 계속 틀려서 포기했었습니다..

 

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의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

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

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4
10 20 30 50

---

풀이 과정 정리

이 문제는 여느 LIS와 같은 방식으로 풀이하는데, 조금 다른 점은 가장 긴 증가하는 부분 수열의 길이만을 구하는 것이 아니라 그 부분 수열 중에서 하나를 출력해야 정답 처리가 된다는 점입니다.

 

구하는 방법은 생각보다 어렵지 않습니다.

2차원 배열을 선언해서 사용

원래 1차원 배열을 이용해서 가장 긴 증가하는 부분 수열을 찾았다면, 한 차원을 더 추가한 2차원 배열을 사용해서 가장 긴 길이를 갱신하기 위해서 사용한 이전 원소의 위치(index)를 기록하는 방식을 도입하면 됩니다.

 

arr배열은 전체 수열을 저장하는 배열이고, d가 기록하기 위해 사용한 2차원 배열입니다.

 

이런 식으로 구현합니다.

그렇게 해서 0번째 값은 길이 자체를 담고, 1번째 값에는 이전 원소의 위치를 담으면서 bottom up 방식으로 진행합니다.

 

이 과정으로 dp 방식을 구현해서 전체 배열의 원소 중에서 마지막 원소가 해당 원소일 때 가장 긴 증가하는 부분 수열을 갖는 원소 하나를 골라 그 원소부터 역추적하면 됩니다.

저는 이런 식으로 역추적을 구현했습니다.

d배열의 2번째 차원에서 1번째 값이 자기 자신을 가리키는 경우 역추적으로 종료하고, 역추적하면서 원소의 값을 vector에 저장합니다.

 

이렇게 벡터에 저장된 원소를 마지막에는 역순으로 출력하면, 가장 긴 증가하는 부분 수열 중 하나를 구할 수 있습니다!

---

제출한 코드 (C++)

#include <iostream>
#include <vector>

#define MAX 1001

using namespace std;

int N;
// index: 수열의 index, 1st value: length, 2nd value: prev index
int d[MAX][2];
int arr[MAX];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N;

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

		// 길이와 이전 index를 초기화한다.
		d[i][0] = 1;
		d[i][1] = i;
	}

	for (int i = 1; i <= N; i++) {
		int currentValue = arr[i];
		int currentIdx = i;
		for (int j = 0; j < i; j++) {
			int prevValue = arr[j];
			int prevIdx = j;
			// i번째 배열의 원소 이전 원소들을 하나씩 살펴본다.
			if (currentValue > prevValue) {
				// 기존 원소가 가장 큰 값일 때의 최대 길이 증가하는 부분 수열의 길이를 갱신할 수 없는 경우
				if (d[currentIdx][0] > d[prevIdx][0] + 1) {
					continue;
				}
				// 최대 길이를 갱신할 수 있는 경우, 길이와 이전 index를 갱신한다.
				else {
					d[currentIdx][0] = d[prevIdx][0] + 1;
					d[currentIdx][1] = j;
				}
			}
		}
	}

	int maxLength = 0;
	int maxIdx = 1;

	for (int i = 1; i <= N; i++) {
		if (maxLength < d[i][0]) {
			maxLength = d[i][0];
			maxIdx = i;
		}
	}

	vector<int> res;
	while (1) {
		// 자기 자신이 가장 긴 증가하는 부분 수열의 마지막인 경우 종료한다.
		if (maxIdx == d[maxIdx][1])
			break;
		// 부분 수열의 이전 원소로 이동하면서 하나씩 vector에 넣는다.
		res.push_back(arr[maxIdx]);
		maxIdx = d[maxIdx][1];
	}

	cout << maxLength << '\n';

	for (int i = res.size() - 1; i >= 0; i--) {
		cout << res[i] << " ";
	}

	return 0;
}