가장 긴 증가하는 부분 수열

Memo

1. 처음 생각 (틀렸음)

처음 이 문제를 생각할 때에는 첫번째 인덱스부터 max값을 바꿔가면서 큰 값을 찾아나가면 된다고 생각했다. 하지만 이번 문제에서는 아래와 같은 입력이 들어왔을때 출력을 고려해야 한다.

{20, 40, 1, 2, 3, 4}

즉 언제 어디서 가장 긴 증가하는 부분수열이 나올지 모르는 것이다.

따라서 DP배열을 사용해서 해당 문제를 접근하였다.

2. dp 적용하기

첫 시도는 방문한 인덱스에서 N까지 가면서 max값보다 큰 값이 나오면 result를 늘려주는 방식으로 구현하였다. 하지만 이렇게 하니 dp배열이 제대로 작동하지 않았다. 그래서 반대로 0에서 현재 방문한 인덱스까지 나보다 작은 칸의 개수를 세기로 하였다.

아래는 배열이 들어왔을 때, dp[3]을 구하는 방법이다.

루프를 통해 0 ~ N - 1(즉, 2)까지 돌면서 기존에 저장해 나가던 값과 해당 인덱스에서의 최대값을 비교해서 결과를 도출한다.

Code

제출 날짜

2021/02/23

메모리

2016 KB

시간

0 ms

#include <iostream>
#include <vector>

int N;
int result;
std::vector<int> arr;
std::vector<int> dp;

void output()
{
	std::cout << result;
}

void solution()
{
	for (int i = 0 ; i < N ; i++)
	{
		for (int j = 0 ; j < i ; j++)
		{
			if (arr[i] > arr[j])
				dp[i] = std::max(dp[i], dp[j] + 1);
		}
		result = std::max(result, dp[i]);
	}
}

void input()
{
	std::cin >> N;
	arr.resize(N);
	dp = std::vector(N, 1);
	for (int i = 0 ; i < N ; i++)
		std::cin >> arr[i];
}

void preset()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);
}

int main()
{
	preset();
	input();
	solution();
	output();
}