[백준 15966] 군계일학 (C++)

문제링크 : https://www.acmicpc.net/problem/15966

15966번: 군계일학

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int arr[100001];
int dp[1000001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N, result = 0;
    cin >> N;
    for(int i=1; i<=N; i++)
    {
        cin >> arr[i];
    }

    for(int i=1; i<=N; i++)
    {
        dp[arr[i]] = max(1, dp[arr[i]-1]+1); //처음이면 1, 그전값이 있다면 그전값 + 1
        result = max(result, dp[arr[i]]);
    }

    cout << result;
    
}

DP문제이다.

그전값이 존재한다면 그전값에 + 1을 더해준 것을 저장하고(길이 연장),

그전 값이 존재하지 않다면 현재 값이 길이의 첫 시작이므로 1을 저장해준다.