[C++] 백준 11053번 가장 긴 증가하는 부분 수열 :: seoftware

문제

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

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

소스코드

#include <iostream>
using namespace std;
int arr[1001];
int dp[1001];

int main(void) {
	//input
	int N; cin >> N;
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	//perform
	int answer = 0;
	for (int i = 1; i <= N; i++) {
		int max = 0;
		for (int j = 0; j < i; j++) {
			if (arr[j] < arr[i] && dp[j] > max) {
				max = dp[j];
			}
		}
		dp[i] = max + 1;
		if (dp[i] > answer) answer = dp[i];
	}
	//output
	cout << answer << endl;
}

코드설명

0. 예를 들어, 10 20 10 30 20 50 의 수열이 있다고 가정해보자. 이 수열을 arr에 순서대로 저장하면 arr[1] = 10, arr[2] = 20, ..., arr[6] = 50 이 저장된다. 

1. 0부터 6(N)까지의 수에 해당하는 증가하는 수열을 dp 배열에 저장할 것이다. arr[i] 일 때 arr[0] 부터 arr[i-1] 까지의 수 중에서 자기(arr[i])보다 값이 작은 것 중에서 dp 값이 가장 큰 값에 +1을 하여 저장한다. 

arr[0] = 0	arr[1] = 10	arr[2] = 20	arr[3] = 10	arr[4] = 30	arr[5] = 20	arr[6] = 50
dp[0] = 0	dp[1] = 1	dp[2] = 2	dp[3] = 1	dp[4] = 3	dp[5] = 2	dp[6] = 4
arr, dp 모두 전역변수 이므로 0으로 초기화	arr[1] 은 arr[0]가 자기보다 값이 작으면서 dp값도 최대이므로(비교할게 없음) dp[1] = dp[0] + 1 = 1이 된다.	arr[2]는 arr[0]부터 arr[1] 중에 arr[1]이 조건에 만족하므로 dp[2] = dp[1] + 1 = 2 가 된다.	arr[3]은 arr[0]부터 arr[2] 중에 arr[0]이 조건에 만족하므로 dp[3] = dp[0] + 1 = 1이 된다.	arr[4]는 arr[0]부터 arr[3] 중에 arr[2]가 arr[4]보다 작으면서도 dp값이 최대이기 때문에 dp[4] = dp[2] + 1 = 3 이 된다.	arr[5]는 arr[0]부터 arr[4] 중에서 arr[1]가 arr[5]보다 작으값 중에 dp값이 최대이기 때문에 dp[5] = dp[1] + 1 = 2이 된다.	arr[6]는 arr[0]부터 arr[5] 중에 arr[4]가 arr[6]보다 작으면서도 dp값이 최대이기 때문에 dp[6] = dp[4] + 1 = 4 이 된다.

3. dp 값을 저장하는 도중에 total maximum 을 변수 answer 에 저장하여 최종 출력은 answer을 출력하면 된다.