[C++] 백준(BOJ) - 14002 : 가장 긴 증가하는 부분 수열 4(LIS)

30 Mar 2024 in Develop on C++, Algorithm

인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.

• 문제
• 입력
• 출력
• 알고리즘
• 풀이
• 코드
• 평가

문제

BOJ - 14002 : 가장 긴 증가하는 부분 수열 4(LIS)(링크)

수열 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 ≤ $A_i$ ≤ 1,000)

출력

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

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

알고리즘

1. LIS (Longest Increase Sequence)

풀이

• prev_list[]를 사용하여 이전 인덱스를 저장

코드

// BOJ - 14002 : 가장 긴 증가하는 부분 수열 4
#include <bits/stdc++.h>
using namespace std;

const int INF = 2147000000;
int n, a[1004], cnt[1004], res = 1, idx;
int prev_list[1004];
vector<int> v;

void go(int idx)
{
	if (idx == -1) return;
	v.push_back(a[idx]);
	go(prev_list[idx]);
	return;
}

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

	cin >> n;

	for (int i = 0; i < n; i++) cin >> a[i];
	fill(prev_list, prev_list + 1004, -1);
	fill(cnt, cnt + 1004, 1);

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (a[j] < a[i] && cnt[i] < cnt[j] + 1)
			{
				cnt[i] = cnt[j] + 1;
				prev_list[i] = j;
				if (res < cnt[i])
				{
					res = cnt[i];
					idx = i;
				}
			}
		}
	}

	cout << res << '\n';
	go(idx);
	for (int i = v.size() - 1; i >= 0; i--) cout << v[i] << " ";

	return 0;
}

평가

• Trace를 추가하기 위한 로직 추가
• 이전 인덱스와 그 값을 저장할 수 있게 prev_list라는 배열과 vector를 사용