백준 11053번: 가장 긴 증가하는 부분 수열(C++)

www.acmicpc.net/problem/11053

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

코드

#include <iostream>
using namespace std;

int n; // 수열 A의 크기.
int arr[1000]; // 수열 A를 이루고 있는 Ai.
int dp[1000]; // Ai를 마지막 수로 갖는 수열 중 가장 긴 길이.

int max_len = 1; // 가장 긴 수열의 길이.

int max(int a, int b){
	return a > b ? a: b;
}

void init(){
	cin >> n;
	for(int i=0; i<1000; i++){
		cin >> arr[i];
	}
}

void solve(){
	for(int i=0; i<n; i++){
		dp[i] = 1;
		for(int j=0; j<i; j++){
			if(arr[i] > arr[j]){
				dp[i] = max(dp[i], dp[j] + 1);
				max_len = max(max_len, dp[i]);}
        }
	}
	cout << max_len;
}


int main() {
	init();
	solve();
}

문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 10-20-30-50으로 4이다.

 

DP를 사용해서 푸는 문제입니다.

물론 모든 경우의 수를 다 탐색해서 풀 수 도 있겠지만... 아마 시간초과가 나겠죠.

문제 지문 자체는 설명이 크게 필요 없을정도로 단순합니다.

 

풀이

우선, 변수부터 간단히 정리하고 넘어가겠습니다.

int n; // 수열 A의 크기.
int arr[1000]; // 수열 A를 이루고 있는 Ai.
int dp[1000]; // Ai를 마지막 수로 갖는 수열 중 가장 긴 길이.

그럼 문제에 나와 있는 예제를 통해 점화식을 알아보도록 해보겠습니다.

주어진 수들입니다. 이 수들은 배열 arr에 들어온 순서대로 저장되어있습니다.

1. arr[0] 으로 끝나는 수열 중 최장 길이

이건 간단합니다. arr[0]이 처음 시작하는 수 이므로 당연히 길이는 1입니다.

 

2. arr[1] 으로 끝나는 수열 중 최장 길이

arr[1]로 끝나게 되면 선택지가 2가지가 있습니다.

1. arr[1] 이 arr[0]보다 크다면(즉, 증가하는 수라면), arr[0]->arr[1] 이렇게 수열이 이루어진다. 이는 dp[0] + 1과 같다.

2. arr[1] 자기자신만으로 이루어진 수열, 길이 1

위 두 가지 선택지의 결과 중 큰 값이 dp[1]의 값이 됩니다.

위의 그림을 보시면 알겠지만, arr[1]은 arr[0]보다 크죠. 'T' 라고 표기했습니다. 그렇기에,

첫 번째 선택지의 값은 dp[0] + 1 = 2 입니다.

두 번째는 자기자신이니까 1이 되죠.

2와 1 중 큰 값인 2가 dp[1]의 값이 됩니다. 그럼 계속해서 보겠습니다.

 

3. arr[2] 으로 끝나는 수열 중 최장 길이

2. arr[1] 으로 끝나는 수열 중 최장길이와 동일하게 접근하시면 됩니다.

그러면 선택지는 3가지가 되겠죠?

하지만 arr[2]와 비교해서 arr[0], arr[1]은 둘 다 arr[2]과 같거나 큰 수 이므로 dp[2]는 자기자신으로 이루어진 수열

길이가 1이 됩니다.

이쯤 되면 점화식이 눈에 들어오실 겁니다.

만약 arr[i] 가 arr[j] 보다 크면(증가하는 수열을 충족하면)
dp[i] = dp[j] + 1

단, 0 <= j < i 이므로 j의 범위 내에서 가장 큰 값이 dp에 저장이 된다.

 

4. arr[3] 으로 끝나는 수열 중 최장 길이

위에서 설명을 다 했다고 생각하고 이제 끝날때까지 표로만 보여드리겠습니다.

 

5. arr[4] 으로 끝나는 수열 중 최장 길이

 

6. arr[5] 으로 끝나는 수열 중 최장 길이

 

마지막으로 DP[n-1] 까지 다 구했다면

가장 긴 수열의 길이를 찾아야 하니, DP 배열 내에서 가장 큰 값을 출력해 주면 정답이 됩니다.