[백준 11053]-가장 긴 증가하는 부분 수열(C++)

📕문제

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 20, 10, 30, 20, 50}인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이다.

---

📕입력

첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000)이 주어진다.

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

---

📕출력

첫째 줄에 수열 A의 가장 긴 증가하는 부분 수열의 길이를 출력한다.

---

💡문제 해석

• 전형적인 DP문제이다.
• 이중 포문을 사용
  • 기준이 되는 원소와 처음부터 기준까지의 구간을 정함.
  • 기준이 되는 원소가 구간 내의 원소보다 크다. (ary [i]>ary [j])
    • DP [i]= max(DP [i], DP [j]+1)
      • j는 탐색하는 원소, 기준이 되는 원소가 크다면 그때의 저장된 값을 한 칸씩 증가시킨다.
  • DP [0]=1이다. 나는 0으로 DP 배열을 초기화시켰기 때문에 마지막에 구한 길이에 +1을 해줬다.

📃코드

// 11053
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
vector<int> ary, cnt, include;
vector<vector<int>>DP;
#define MAX 1001
int main()
{
    cin >> n;
    ary.resize(n + 1, 0);
    vector<int>dp(n,0);
    for (int i =0; i < n; i++)
    {
        cin >> ary[i];
    }
    //포함하고 포함안하고를 정하자.
    // DP[i][j]에서 i는 현재 탐색한 원소의 수로 하고, j를 현재 내가 담은 원소중에서 가장 큰수로 할까?
    // 그럼 DP[i][j]의 값은 길이로 하면 되겟당.!
    int nowV = 0, Cnt = 0, oldV = 0, CurV = 0;
    for (int i = 0; i <n; i++) //i는 기준이 되는 원소
    {
        for(int j=0; j<i;j++) //j는 0~기준 전까지 찾는것.
        {
            if(ary[i]>ary[j])
            {
                dp[i]=max(dp[i],dp[j]+1);
            }
        }
    }
    int max=0;
    for(auto a: dp)
    {
        if(max<a)
        {
            max=a;
        }
    }
    cout<<max+1;
}

---

느낀 점

• DP 어렵다 x 1000000.