가장 긴 감소하는 부분 수열
DP풀이
이전에 풀었던 연속합과 같은 느낌으로 dp[i]를 i번째 항을 포함하는 가장 긴 감소하는 부분수열로 정했다.
i부터 j까지 어느 시작점과 끝지점이 있는 선택문제는 i번째항을 포함하는 dp로 정하면된다.
dp[i]를 어떻게 식으로 표현해야 할지 예시를 들어 설명하겠다.
수열 A = { 1, 6, 5, 7, 2, 4 }, dp[6]을 구해보자
앞에서 부터 추가할 항을 선택해야 한다.
선행조건으로 4보다는 커야한다.
j=1, 1 < 4 (x)
j=2, 6 > 4 (o), 6을 추가하고 수열은 {6, 4}로 길이는 2가 된다.
j=3, 5 > 4 (o), 이때 5를 추가하는것이 가장 긴 수열을 만들 수 있을지 알아보자
먼저 dp[3]는 2이다. dp의 최적의 원리에 따라 dp[3]에 해당하는 수열 {6, 5}에 4가 추가한다. 수열은 {6, 5, 4} 길이는 3이된다.
j=4, 7 > 4 (o), dp[4] =1이므로 해당하는 수열 {7}에 4를 추가해 {7,4}라는 수열을 만들어도 길이가 3보다 작다. 따라서 추가하지 않는다.
j=5, 2 < 4 (x)
j=6, dp[6] = 3 이된다.
실제 코드
#include <iostream>
#include <vector>
#include <algorithm>
#include <fstream>
#include <math.h>
#include <string>
#include <set>
using namespace std;
#define endl "\n"
#define MAX 1000+1
int N;
int dp[MAX];
int numList[MAX];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//ifstream cin; cin.open("input.txt");
cin >> N;
for (int i = 1; i <= N; i++)
{
cin >> numList[i];
dp[i] = 1;
for (int j = 1; j <= i; j++)
{
if (numList[i] < numList[j] && dp[j]+1 > dp[i])
{
dp[i] = dp[j] + 1;
}
}
}
int ans = 0;
for (int i = 1; i <= N; i++)
{
ans = max(ans, dp[i]);
}
cout << ans;
}dp문제는 항상 문제를 봤을때 머리가 하얘지고, 막상 풀이를 보면 매우 간단한 코드들이 적혀있고 그것들은 한번에 이해가안되고, 그것이 이해하려 노력하다보면 어느순간 포인트를 캐치하고 이해가 된다.
