코딩생존기

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

가장 긴 증가하는 부분 수열 LIS를 해결하는 방법 중에 DP를 사용해서 풀어보겠다. 

주어진 배열의 각 위치에 대해, 그 위치까지의 LIS 길이를 저장하는 벡터를 만들고 처음에는 각 원소가 자기 자신만 포함하더라도 수열의 길이는 1이므로, dp 배열의 모든 값을 1로 초기화한다. 

dp[i]는 i번째 원소를 마지막으로 하는 가장 긴 증가 부분 수열의 길이이고 이를 구해야한다. 

예제 입력을 바탕으로 설명해보자면 

• i=1 (값: 10)
  • 10보다 앞에 있는 수가 없으므로, dp[1] = 1.
  • 현재 dp 상태: [1, 1, 1, 1, 1, 1]
• i=2 (값: 20)
  • 앞에 있는 수 10은 20보다 작으므로, dp[2] = dp[1] + 1 = 2.
  • 현재 dp 상태: [1, 2, 1, 1, 1, 1]
• i=3 (값: 10)
  • 앞에 있는 수 중 10보다 작은 수는 없으므로, dp[3] = 1.
  • 현재 dp 상태: [1, 2, 1, 1, 1, 1]

이런식으로 검사를 하면서 DP의 값을 업데이트해주고 가장 긴 값을 저장해서 출력해주면 된다.

정답코드

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;

	cin >> n;

	vector<int> v(n);
	vector<int> dp(n,1);

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	int answer = 1;

	
	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < i; j++)
		{
			//기준값보다 작은게 몇개인지 센다.
			if (v[i] > v[j])
			{
				dp[i] = max(dp[i], dp[j] + 1);
			}
		}
		answer = max(answer, dp[i]);
	}

	cout << answer << "\n";

	return 0;
}