[DP] BOJ 11053 가장 긴 증가하는 부분 - 오답노트

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

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

 

- 문제 파악

주어진 수열에서 부분적으로 제거 하여 증가하는 수열을 만들 때 가장 긴 수열의 길이를 출력하라

 

- 나의 접근

1. 0부터 N까지 주어진 배열을 확인하며, arr[i] 와 가장 차이가 적게 나는 배열을 찾아 거기에 arr[i]+1 값을 넣도록 했다.

-> 경우의 수를 너무 좁혀서 다 안찾아지는 그런 경우가 발생하는듯..

 

2. 3중 for문을 사용.. 당연히 시간초과

 

- 정답

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

최장 증가 부분 수열 - 나무위키

 

유명한 알고리즘인가 보다 나무위키에도 실려있을 정도면..

 

배열 D는 arr[i] 가 수열의 마지막일때 수열의 길이를 넣는 배열이다.

나의 접근 1번과 비슷하지만, arr[i] 뒤에 붙을 수 있는 모든 경우의 수 중에서 가장 길이가 긴 경우를 arr[i]에 더해 D[i]에 넣어준다.

 

#include "bits/stdc++.h"

using namespace std;

int n;
int D[1001]; 
int arr[1001];
int ans = 1;


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

	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];

	fill(D, D + 1001, 1);
		
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			if (arr[i] <= arr[j])
				continue;

			D[i] = max(D[j] + 1, D[i]);
			ans = max(D[i], ans);

		}

	}

	cout << ans;

}