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

www.acmicpc.net/problem/11053

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

이 문제는 앞의 결과가 뒤의 결과와 관련이 있으므로 규칙을 찾아서 점화식을 만들어서 푸는 DP문제이다.

 

n을 하나씩 증가시켜가며 점화식을 세운다.

n = 1 일 때는 자기 자신 뿐이므로 가장 긴 증가하는 부분 수열의 길이는 1이다.

n >= 2 일 때는 만약 앞에 자기 자신보다 낮은 숫자가 있다면, 해당 숫자까지로 이루어진 부분수열로 만들수 있는 가장 긴 증가하는 부분수열의 뒤에 자기 자신을 붙여서 더 큰 증가하는 부분수열을 만들 수 있으므로 해당 지점에 길이값 + 1 만큼의 길이를 가질 수 있다.

 

코드로 구현하면 다음과 같다.

#include <iostream>

using namespace std;

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

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	int max_val = 0;
	int arr[1000] = { 0, };
	int dp[1000] = { 0, };

	cin >> N;
	for (int i = 0; i < N; i++) { cin >> arr[i]; }
	for (int j = 0; j < N; j++) {
		for (int i = j - 1; i >= 0; --i) {
			if (arr[j] > arr[i]) dp[j] = max(dp[j], dp[i] + 1);
		}
	}
	for (int i = N - 1; i >= 0; --i) max_val = max(max_val, dp[i]);
	cout << max_val + 1;
	return 0;
}

만약 당신이 이 문제의 반례를 찾다가 이 블로그를 방문했다면

 

3

3 1 2 

 

를 입력해보자. 답은 2다. 만약 dp배열의 값이 0으로 초기화 되어있는 상태에서 dp[0] = 1을 주고 이중포문을 돌면서

if (arr[j] > arr[i]) dp[j] = max(dp[j], dp[i] + 1);

위와 같은 방법으로 dp값을 갱신시켜줬다면, 아마 답이 1이 나올 것이다. 그 어떤 값도 arr[0]보다 크지 않기 때문에 dp[0]은 무시된다. 따라서 모든 값을 1로 초기화 시켜주고 dp를 돌리던지 아니면 위의 코드처럼 아예 dp[0] = 0으로 두고 값을 구한 뒤 (max_val + 1) 을 해주면 된다.