[DP] BOJ 11053 번 문제 풀이

문제분석

 

DP 유형의 문제들은 점화식을 도출하는 것이

문제의 전부입니다!!

 

 

D[i] = i 번째 인덱스를 마지막으로 하는 수열의 최대 길이

arr[i] = 주어진 수열

이라고 정의하고 시작하겠습니다.

 

그러면, D[1] = 1 은 자명합니다.

 

D[2] 부터는 주어진 수열의 데이터를 비교해야 합니다.

 

1. 이전 값 중에 arr[2] 보다 작은 값들을 모두 후보 인덱스로 둡니다.

2. D[후보 인덱스] 중에 최댓값을 구합니다. 

3. 그 최댓값에 자기 자신인 1을 더해줍니다.

 

설명이 조금 복잡하니 예시문제로 다시 봅시다.

 

10 20 10 30 20 50

 

이러한 수열이 있습니다.

이때, D[4] 를 구하고자 합니다.

그러면 우선 arr[4] = 30 의 값 보다 작은 값들을 

이전 인덱스에서 색출합니다.

 

10 20 10 30 20 50

 

초록색 친구들이 되겠네요. ㅎㅎㅎ

이 친구들의 인덱스는 1, 2, 3 입니다. 

 

그러면 이미 구해져 있는 D[1], D[2], D[3] 중 최댓값을 찾고

 

D[4] = MAX + 1

 

자기 자신을 포함한 길이를 출력해야 하니 1을 더해주면 되겠네요.

 

 

코드

 

#include "bits/stdc++.h"

using namespace std;

int d[1005];
int arr[1005];

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;

	cin >> n;
	//입력된 수열 저장
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	d[0] = 1; // 항상 자명한 값

	for (int i = 1; i < n; i++)
	{
		int mx = 0;

		for (int j =0; j < i; j++)
		{
			if (arr[i] > arr[j])
			// 현재 인덱스 보다 작은 경우
			{
				mx = max(mx, d[j]);
			}
		}
		d[i] = mx + 1;
	}// 가장 긴 수열에 자신(1)을 더함
	cout << *max_element(d, d + n + 1);
	//배열 값 중 가장 큰 값 출력
	return 0;
}