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

https://www.acmicpc.net/problem/11053

10

1 2 3 4 1 2 3 4 5 6

만약 위 예제입력

풀이

1. d[i] = i번째에서 가질 수 있는 모든 부분수열의 최대 길이로 설정

2. j = 0 ~ i 까지 수열을 순회

3. i 번째 수 보다 j 번째 수가 더 작고, d[j] + 1 이 d[i] 보다 크다면 새로 값을 설정한다.

위 풀이를 차근 차근 따져보면 아래 그림과 같다.

말로 설명하기보다 그림이 편할 것 같아서 노가다함

간단하게 말해서, 현재 i 번째 숫자까지 수열의 최대 길이를 계산하는 로직을

[0 ~ 1], [0 ~ 2], ... [0 ~ N] 까지 반복하는 것이다.

#include <iostream>
#define MAX 1000 
using namespace std;
int main()
{
    int a[MAX + 1] = {0, };
    int d[MAX + 1] = {0, };
    int N;
    
    scanf("%d", &N);
    for (int i = 0; i < N; ++i) {
        scanf("%d", (a + i));
    }
    
    for (int i = 0; i < N; ++i) {
        d[i] = 1;
        for (int j = 0; j < i; ++j) {
            if (a[j] < a[i] && d[j] + 1 > d[i]) {
                d[i] = d[j] + 1;
            }
        }
    }
    
    int result = 0;
    for (int i = 0; i < N; ++i) {
        result = max(result, d[i]);
    }
    printf("%d\n", result);
    
    return 0;
}