[알고리즘_PS] boj 11722 가장 긴 감소하는 부분 수열 by Cpp

문제

코드

#include <iostream>
#include <algorithm>
using namespace std;

int dp[1001] = {
    0,
};
int arr[1001] = {
    0,
};

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    fill(dp, dp + 1001, 1);

    int n = 0;

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

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j <= i; j++)
        {
            if (arr[i] < arr[j])
            {
                dp[i] = max(dp[j] + 1, dp[i]);
            }
        }
    }

    int max_len = *max_element(begin(dp), end(dp));

    cout << max_len;
    return 0;
}

 

풀이

저번주에 풀기 시작했었는데, 그 당시에는 아이디어가 떠오를랑 말랑 하다가 포기하고 오늘 다시 도전했더니 잘 풀렸다 ㅎㅎ

dp[i]에 들어가는 값은

1. 우선 초기화로 모두 1 값을 준다. 수 하나로도 길이가 1인 순열이 만들어지기 때문(말이이상해요..)
2. arr[0] ~ arr[i]을 범위로하고,
3. arr[i]를 감소하는 부분 수열의 마지막 수로 하는 감소하는 부분 수열의 길이

아래 그림을 보면 이해가 더 쉽다.

dp[4]를 채울 때를 생각해보자. (i = 4일 때!!)

 

dp[4]는 처음에 1으로 초기화되어있다. j값이 증가하는 for문을 돌면서, j = 0일 때 우선 arr[0]의 값이 3으로 arr[4]인 3보다 크므로 dp[4]의 값은 dp[0] + 1(=2)로 변경된다.

 

j값이 한번 더 증가해 j는 1이 된다. arr[1]의 값이 4이므로 arr[4]보다 크지만, 이미 dp[4]의 값이 2이기 때문에 dp[1]+1로 변경되지 않는다. (바뀌어도 큰 상관은 없다 !) j가 2가되어서도 동일하게 처리한다.

 

j값이 증가해서 3이 되면, arr[3] > arr[4]이고, dp[3] + 1 > dp[4](현재 2)기 때문에 dp[4]의 값이 3으로 갱신되며 dp[4]값이 정해지고, i값이 1 증가하면서 로직이 반복되며 dp 테이블이 채워진다.

 

위와 같은 방식으로 dp 테이블을 채우고, 마지막에 dp 테이블에서 가장 큰 값을 찾고 출력하고 끝!