[알고리즘] 가장 긴 증가하는 부분 수열 - 백준 11053

문제

 

 

풀이

표를 그려서 생각하는 것이 좋을 것 같다.

index	0	1	2	3	4	5	6
arr	0	10	20	10	30	20	50
dp	0

 

내가 생각한 방법은 간단하다. 

arr[0] ~ arr[i - 1]까지 탐색을 하며 arr[i]가 속할 수 있는 수열 중 가장 긴 수열의 길이를 dp[i]에 저장하는 것이다. 

 

1. arr[0] ~ arr[i-1]까지 탐색

2. 탐색 중 arr[i]보다 작은 값을 발견하였고 그 값의 dp값이 지금까지의 dp값보다 작다면 발견한 수의 dp값을 따로 저장

3. 탐색 종료 후 dp[i] = 발견한 가장 큰 dp값 + 1로 수열 길이 구하기

 

위의 로직으로 dp값을 구하면 아래처럼 구해진다.

index	0	1	2	3	4	5	6
arr	0	10	20	10	30	20	50
dp	0	1 (dp[0] + 1)	2 (dp[1] + 1)	1 (dp[0] + 1)	3 (dp[2] + 1)	2 (dp[1] + 1)	4 (dp[4] + 1)

 

이 문제는 길게 설명할 필요 없이 코드를 보는 것이 좋을 것 같다.

 

 

코드

#include<iostream>
using namespace std;

int arr[1001], dp[1001], n;

int solution()
{
	int maxNum = 0;

	for (int i = 1; i <= n; i++)
	{
		maxNum = 0;
		
        //1. 0 ~ i ~ 1까지 탐색
		for (int j = 0; j < i; j++)
		{
        	//2. 최대 수열 길이 갱신
			if (arr[i] > arr[j])
			{
				maxNum = max(maxNum, dp[j]);
			}
		}
		
        //3. dp값 저장
		dp[i] = maxNum + 1;
	}

	for (int i = 1; i <= n; i++)
		maxNum = max(maxNum, dp[i]);

	return maxNum;
}

int main()
{
	cin >> n;

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

	cout << solution();
}