[ 백준 11722 ] 가장 긴 감소하는 부분수열 (C++)

백준의 가장 긴 감소하는 부분수열(11722) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 먼저 쉬운 예로 어떨 때 가장 긴 감소하는 부분수열이 생성되는지 한번 알아보고 문제에 접근해보자.

   수열 A = { 1, 6, 5, 7, 2, 4 } 가 있다.

   먼저 1일 때 가장 긴 감소하는 부분수열의 길이는 얼마일까?? 숫자가 1개 뿐이니 1일 것이다.

   그렇다면 6일 때는 어떻게 될까???

   6과 6앞에 있는 1을 비교했을 때, 1 < 6 이므로 가장 긴 감소하는 부분수열은 1일 것이다.

   5 일 때는?? 앞에 있는 1과 6을 순서대로 비교해서, 결과가 { 6, 5 } 로 길이가 2가 나올 것이다.

   7 일 때는?? 앞에 있는 1,6,5를 순서대로 비교해서 결과과 { 7 } 로 길이가 1이 나올 것이다.

   2 일 때는 { 6, 5, 2 }로 길이가 3.

   4 일 때는 { 6, 5, 4 }로 길이가 3. 이래서 최대길이는 3이 될 것이다.

  

   본인은 이 최대길이를 저장하기 위해서 DP[] 1차원 배열을 사용하였다.

   DP[a] = b 의 의미는 "a번 Index까지의 최대길이는 b입니다." 가 된다.

  

2) 1)에서 보았듯이, 해당 인덱스보다 더 작은 번호의 인덱스들을 모두 비교하면서, DP[] 값을 갱신해 주면 된다.

   현재 인덱스와, 더 작은 인덱스들을 비교했을 때, 더 작은 인덱스의 값이 더 크고,

   이 인덱스를 선택했을 때의 길이가 기존의 길이보다 더 길어진다면 길이를 갱신해 주면 된다.

   위의 말을 구체적으로 알아보자. 내가 읽어도 이해가 안된다.

   2가지 조건을 충족하면서 길이를 갱신해주면된다.

   1. 더 작은 인덱스 값이 현재 인덱스의 값 보다 더 큰가?

   2. 현재 비교하고 있는 이 인덱스의 값을 선택하는 것이, 최대길이가 될 수 있는가?

   위에 문제에서 '2'에 집중하자.

   2는 1, 6, 5, 7 총 4개의 숫자와 비교를 할 것이다.

   ( 2 = 현재 Index의 값, 1,6,5,7 = 더 작은 Index의 해당 값들)

   1과 비교했을 때, 더 작은 Index의 값이 더 작으므로 Pass.

     - 1. 더 작은 인덱스의 값이 현재 인덱스의 값 보다 더 큰가 ? 만족하지 않는다. Pass (1 < 2)

   6과 비교했을 때

     - 1. 더 작은 인덱스의 값이 현재 인덱스의 값 보다 더 큰가 ? 더 크다. (6 > 2)

     - 2. '6'을 선택함으로써 { 6, 2 } 가 최대 길이가 될 수 있는가?

          - 현재길이는 { 2 } 로 길이가 1.

          - { 6, 2 } 가 나오게 되는 이유는 6일 때 최대길이는 { 6 } 으로써 하나 이므로 여기서 + 2 가 된 모양.

           - 만족한다.

   < 현재까지 최대갈이 { 6, 4 } 로 2 >

   5와 비교했을 때

     - 1. 더 작은 인덱스의 값이 현재 인덱스의 값 보다 더 큰가 ? 더 크다. (5 > 2) 

     - 2. '5'를 선택함으로써 { 6, 5, 2 } 가 최대 길이가 될 수 있는가?

          - 현재 최대길이는 { 6, 2 } 로 길이가 2.

          - { 6, 5, 2 } 가 나오게 되는 이유는 5 일 때, 최대길이가 { 6, 5 } 로 2가 된다. 여기서 + 2가 되어

            { 6, 5, 2 } 라는 수열이 나오게된다. 길이는 3.

          - 최대길이가 될 수 있다 !

   7과 비교했을 때

     - 해보면 최대길이가 나올 수가 없음.

   이렇게 해당 숫자를 선택했을 때, 현재 최대길이보다 1칸 만큼 더 길어질 수 있는지 판단을 해주면 된다.

   말이 어렵지 코드를 보면 쉽다.

for (int i = 1; i <= N; i++)
    {
        DP[i] = 1;
        for (int j = 1; j <= i; j++)
        {
            if (Arr[i] < Arr[j] && DP[j] + 1 > DP[i])
            {
                DP[i] = DP[j] + 1;
            }
        }
    }

    이런식으로 !

 

    이런식으로 DP[1] ~ DP[N]의 모든 값을 구하고, 최댓값을 구해주면 된다.

[ 소스코드 ]

#include<iostream>
 
#define endl "\n"
#define MAX 1001
using namespace std;
 
int N;
int Arr[MAX];
int DP[MAX];
 
void Input()
{
    cin >> N;
    for (int i = 1; i <= N; i++)
    {
        cin >> Arr[i];
    }
}
 
void Solution()
{
    for (int i = 1; i <= N; i++)
    {
        DP[i] = 1;
        for (int j = 1; j <= i; j++)
        {
            if (Arr[i] < Arr[j] && DP[j] + 1 > DP[i])
            {
                DP[i] = DP[j] + 1;
            }
        }
    }
 
    int Max = 0;
    for (int i = 1; i <= N; i++)
    {
        if (DP[i] > Max)
        {
            Max = DP[i];
        }    
    }
    cout << Max << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}