[백준/C++] 11053번 : 가장 긴 증가하는 부분 수열 (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 ≤ Ai ≤ 1,000)

출력

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

예제 입력 1

6
10 20 10 30 20 50

예제 출력 1

4

---

📌 LIS

해당 문제는 LIS 수열을 구하는 문제이다.

LIS는 Longest Increasing Subsequence 의 약자로, "최장 증가 부분 수열"을 뜻한다.

 

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

 

나는 처음에 그냥 입력받는 수열 중에서 이전 입력값보다 다음 입력값이 더 큰 경우를 카운팅하면 되는 간단한 문제인 줄 알았는데, 그게 아니었다.

 

문제에는 예제 입력이 하나만 있어서 이해하기가 힘들었는데 다음 반례를 보고 LIS 수열을 이해할 수 있었다.

 

7
30 10 30 70 20 50

 

위 테스트케이스에서 단순히 왼쪽 원소보다 오른쪽 원소가 큰 경우를 카운팅하면 30 10 30 70 20 50 으로 판별되어 2 가 나온다.

그러나, 30보다 작지만 10으로 시작하는 10 20 50 수열의 길이가 3 이므로 더 길다!

 

따라서, 해당 문제는 DP를 이용하는 방식으로 풀이했고, i = 0 부터 i < 총길이 만큼 순차적인 검색을 수행하면서, j = 0 부터 j = i 까지 앞에 원소들을 검사하는 2중 for문을 작성하였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

	int S;
	cin >> S;
	vector<int> A(S);
	for (int& a : A)
		cin >> a;

	int dp[1001];
	fill(begin(dp), end(dp), 1); // memset은 0또는 -1로만 초기화 가능, 다른 숫자는 비트값으로 들어감

	for (int i = 0; i < S; i++)
	{
		for(int j = 0; j < i; j++)
		{
			if (A[i] > A[j])
				dp[i] = max(dp[i], dp[j] + 1);
		}
	}
	sort(begin(dp), end(dp), greater<>());
	cout << dp[0];
	return 0;
}

기본적인 dp[i] 의 모든 원소들은 길이 1 값을 갖는다고 하여 dp[i] = 1; 로 초기화해주었고,

2중 for문을 수행하면서 현재 검사하는 원소 dp[i] 가 앞에 원소들 dp[j] 보다 큰 경우를 dp 값을 수정해주었다.

 

현재 원소의 dp값인 dp[i]와, 앞에 원소들의 dp[j] 값에 현재 원소까지의 카운트값을 합한 dp[j]+1 값을 비교하여 더 큰 값을 dp[i] 값으로 설정해주었다.

 

최종적으로 가장 큰 dp값을 출력해야 하기 때문에 내림차순 정렬을 수행하여 0번째 원소를 출력해주었다.

(오름차순으로 하면 dp 배열의 크기를 최대로 해놨기 때문에 1만 출력됨)

---

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

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