[백준/C,C++] 11053번: 가장 긴 증가하는 부분 수열

www.acmicpc.net/problem/11053

11053번: 가장 긴 증가하는 부분 수열

수열 중 부분 수열을 구하는 문제입니다. 찾아보니 이런 문제 들을 LIS(Longest Increasing Subsequence) 알고리즘이라고 하더라구요. 로직 자체는 크게 어렵지 않습니다. 100, 200, 300, 10, 20, 30, 1, 2, 400이라는 수열이 있다고 가정해보겠습니다.

	1	2	3	4	5	6	7	8	9
100	100	0	0	0	0	0	0	0	0
200	100	200	0	0	0	0	0	0	0
300	100	200	300	0	0	0	0	0	0
10	10	200	300	0	0	0	0	0	0
20	10	20	300	0	0	0	0	0	0
30	10	20	30	0	0	0	0	0	0
1	1	20	30	0	0	0	0	0	0
2	1	2	30	0	0	0	0	0	0
400	1	2	30	400	0	0	0	0	0

표를 보시면 아시다시피 현재 가장 긴 수열의 마지막 값보다 큰 값이 오면 마지막에 값을 넣어주고 가장 긴 수열의 마지막 값보다 작다면 자신보다 큰 값 중 가장 작은 값을 찾아 그 자리에 값을 넣어주면 됩니다. 즉 현재 가장 긴 수열을 업데이트하지 못한다면 이전의 수열을 업데이트하는 것이죠.

#include<iostream>

using namespace std;

#define MAX 1001

int DP[MAX];
int dis;

int main(void)
{
    int N; cin >> N;

    for (int i = 1; i <= N; i++) {
        int temp; cin >> temp;
        if (temp > DP[dis]) {
            DP[++dis] = temp;
        }
        else {
            for (int j = 1; j <= dis; j++) {
                if (temp < DP[j] && temp > DP[j - 1]) {
                    DP[j] = temp;
                }
            }
        }
    }

    cout << dis;

    return 0;
}

처음 보는 문제 유형이라 2시간 정도 고민하다 로직이 번뜩 떠올랐는데, 풀고 보니 조금 허무한 문제였습니다..