[백준/BOJ] 11053번 가장 긴 증가하는 부분 수열 (C/C++)

백준 온라인 저지(BOJ) 11053번 가장 긴 증가하는 부분 수열

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

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

* 사용언어 : C언어, C++

 

1. 문제

주어진 수열에 대해서 가장 긴 증가하는 부분 수열의 길이를 출력

 

2. 풀이

Dynamic Programming으로 푸는 대표적인 문제로 LIS(Longest Increasing Subsequence)라고 부릅니다.

비슷한 결의 문제로 ① 감소 버전, ② 바이토닉 버전(증가하다가 감소)도 있습니다.

 

LIS는 개발자 만화에서 사용될 정도로 아주 대표적인 DP문제 중 하나입니다.

출처 : Instagram @waterglasstoon (비상업적 용도로 사용 가능하다고 하심)

 

만만하게 보고 혼자서 풀어보려고 고민해봤는데 아이디어가 안 떠올라서

아래 나무위키 링크에서 풀이법을 공부한 뒤 풀어봤습니다.

https://namu.wiki/w/%EC%B5%9C%EC%9E%A5%20%EC%A6%9D%EA%B0%80%20%EB%B6%80%EB%B6%84%20%EC%88%98%EC%97%B4

최장 증가 부분 수열

(아래 작성한 풀이는 O(N^2) 풀이법으로 O(NlogN) 풀이는 위 링크에서 참고 바랍니다)

 

 

제가 이해한대로 다시 설명해보겠습니다.

1차원 배열 a에 모든 수를 입력받고 같은 크기의 배열 dp를 선언합니다.

 

dp[i]에는 1부터 i번까지 가장 긴 증가하는 부분 수열의 길이가 기록됩니다.

dp[i]를 계산할 때는 1부터 i - 1까지의 숫자를 탐색(index j)하고, 아래 두 조건을 확인합니다.

1) a[j]가 a[i]보다 작은 경우

2) dp[j] + 1이 현재 dp[i]보다 큰 경우

만약 위 두 조건을 만족하면 dp[i]를 dp[j] + 1로 업데이트합니다.

 

1부터 N까지 모든 탐색을 마쳤다면, dp 배열의 모든 값 중 가장 큰 값을 출력하면 됩니다.

 

주의할 점은 후반부에 첫 번째 숫자보다 더 작은 숫자로 LIS를 시작할 수 있기 때문에

a[0]과 dp[0]은 첫 번째 숫자가 아닌 0으로 초기화해야 합니다.

 

관련하여 문제 풀이에 도움이 되었던 반례 2가지 공유드리며 설명 마치겠습니다.

 

1
10

(정답 1)

9
3 5 7 9 1 3 5 6 7

(정답 5)

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
11053_가장 긴 증가하는 부분 수열
1120KB	0ms
*/
#include <cstdio>

const int LM = 1001;
int a[LM], dp[LM], N, max;

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 1; i <= N; ++i) scanf("%d", &a[i]);

	for (int i = 1; i <= N; ++i) {
		for (int j = 0; j < i; ++j) {
			if (a[j] < a[i] && dp[j] + 1 > dp[i]) dp[i] = dp[j] + 1;
		}
		if (dp[i] > max) max = dp[i];
	}

	printf("%d\n", max);
	return 0;
}