[Baekjoon] 백준 1182번 가장 긴 증가하는 부분수열

11053번 가장 긴 증가하는 부분수열 문제 풀이

문제

• 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오.
  예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 30, 50} 이고, 길이는 4이다.

입력

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

출력

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

예제

입력
6
10 20 10 30 20 50

출력
4

코드

#include<iostream>
using namespace std;

int d[1001];
int a[1001];

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

    for (int i = 0; i < n; i++) {
        d[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[i] > a[j] && d[j] + 1 > d[i]) {
                d[i] = d[j] + 1;
            }
        }
    }
    int result = 0;
    for (int i = 0; i < n; i++) {
        if (d[i] > result)
            result = d[i];
    }
    cout << result << '\n';
    return 0;
}

해결방법

• d[i]는 a[1] ~ a[i]가 존재할 때 a[i]를 포함하는 부분집합 원소의 갯수이다.
• a[0] ~ a[5]까지의 원소가 존재할 때 증가하는 부분수열을 찾기 위해서 인덱스가 증가할 때 마다 0번째 인덱스에서 현재 위치하는 인덱스까지 비교하는 작업이 필요하다.

    for (int i = 0; i < n; i++) {
        d[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[i] > a[j] && d[j] + 1 > d[i]) {
                d[i] = d[j] + 1;
            }
        }
    }

• 본인은 항상 수열이 될 수 있으므로 1을 저장해야 한다.
• a[i]와 a[j]를 비교할 때 a[i]의 원소가 a[j]보다 커야만 증가하는 수열이 될 수 있다.
• d[i]의 값을 지정할 때 d[j]는 이미 이전부터 만들어진 수열의 원소 갯수를 가지고 있다. 따라서 그 값들 중 가장 큰 값을 찾아서 +1(본인)을 해줘야한다.
• j는 항상 원소의 처음부터 i번 이전 인덱스 까지 탐색하기 때문에 가장 큰 값을 찾을 수 있다.
• 마지막으로 d[n]배열에서 가장 큰 값을 찾아서 출력한다.

각주

• 항상 첫 번째 원소부터 시작하는것으로 생각해서 풀이 방법에 비해 풀이 시간이 무척 오래걸린 문제였다.