BOJ 15966 군계일학

30 Aug 2020 in Study on BOJ, Dp

사용한 알고리즘

DP

알고리즘 설명

1씩 증가하는 가장 긴 수열 길이를 찾는 문제이다.
순서를 유지하되, 임의에 값들을 제거할 수 있다.
이 문제는 간단하게 1차원 DP 수열을 잡으면 풀린다.
DP(x): 현재 값이 x일때 지금까지 나온 수열 중 1씩 증가하여 x로 끝나는 최대 길이
DP(x) = max(DP(x), DP(x-1) + 1)

풀이

// baekjoon 15966 yechan
#include <bits/stdc++.h>
using namespace std;

const int MAX_N=100001;
const int MAX_V=1000001;

int N, dp[MAX_V];
int x, ret;

int main() {
    scanf("%d", &N);
    for (int i=0; i<N; i++) {
        scanf("%d", &x);
        dp[x] = max(dp[x], dp[x-1] + 1);
        ret = max(ret, dp[x]);
    }
    printf("%d\n", ret);
    return 0;
}