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

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

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

 본 문제는 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 문제다. 수열의 값을 저장하는 배열 a, 긴 부분 수열의 길이를 저장하는 배열 b라고 했을 때, a[i]의 이전 배열의 값과 비교하면서, d[i] 이전의 배열의 값에 1을 더한 값과 비교를 해야한다. 즉, 1 ≤ j < i 일때, ( a[i] > a[j] ) and ( d[i] < d[j] + 1 ) 인 점화식을 정의할 수 있다.

1. 수열 입력
2. d[]을 1로 초기화 (이때, memset을 이용하여 1로 초기화 하는 바보같은 행동을 주의하자)
   • memset을 사용할 때는, true, false, 0 ,-1만 사용해야 한다.
   • 왜냐하면 초기화를 할 때, 바이트 단위로 하기 때문에 만약 1로 할 경우 이상한 값이 저장된다. 
3. ( a[i] > a[j] ) and ( d[i] < d[j] + 1 ) 비교
4. 배열 d 중 제일 큰 값 출력

Bottom-up

#include <cstdio>
#include <cstring>
#include <algorithm>
 
using namespace std;
 
int a[1001];
int d[1001];
 
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    //memset(d, 1, sizeof(d));
    for (int i = 0; i <= n; i++) {
        d[i] = 1;
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            if (a[i] > a[j] && d[i] < d[j]+1)
                d[i] = d[j]+1;
        }
    }
    auto it = max_element(d, d+n+1);
    printf("%d", *it);
}