11568번: 민균이의 계략

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

11568번: 민균이의 계략

카드를 0번째 카드부터 순서대로 오름차순으로 최대한 많이 골라야 하므로, 이 문제는 가장 긴 증가하는 부분 수열을 구하는 문제이다.

i - 1번째 카드까지 사용해 가장 긴 증가하는 부분 수열 lis를 구했다고 하자. i번째 카드에 적힌 값 card_i가 lis의 맨 마지막 카드에 적힌 값보다 크다면 lis의 맨 뒤에 card_i를 추가해 lis의 길이를 늘리고, 그렇지 않다면 lis에서 적힌 값이 card_i보다 작은 카드 중 그 값이 가장 큰 카드를 i번째 카드로 대체해 이후의 값을 갱신할 수 있게 한다. 이 때 카드를 card_i로 대체하는 경우 i번째보다 전에 나온 카드가 i번째에 나온 카드 이후에 위치하므로 부분 수열의 규칙을 무시하지만, 길이 자체는 변하지 않는다.

#include <algorithm>
#include <cstdio>

using namespace std;

#define MAX_N 1000

int main() {
    // N: 카드의 개수, card: 각 카드에 적힌 수
    // lis: 가장 긴 증가하는 부분 수열, len: lis의 길이
    int N, card, lis[MAX_N] = { 0, }, len = 0;

    // 각 수열의 성분에 대해
    for (scanf("%d", &N); N--; ) {
        // 각 수열의 성분을 입력받고
        scanf("%d", &card);
        // 증가하는 부분 수열 lis이 비었거나 card가 lis의 마지막 값보다 크다면
        // lis의 맨 뒤에 card를 추가
        if (!len || lis[len - 1] < card) lis[len++] = card;
        // 그렇지 않다면 lis에서 card보다 작은 값 중 가장 큰 값을 card로 변경
        // 부분 수열의 순서에는 영향을 미치지만 부분 수열의 길이에는 영향을 주지 않음
        else *lower_bound(lis, lis + len, card) = card;
    }

    // 가장 긴 증가하는 부분 수열의 길이를 출력
    printf("%hd\n", len);

    return 0;
}