[백준 11568번] 민균이의 계략 (C++)

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

11568번: 민균이의 계략

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

int N, result;
int arr[1001], dp[1001];

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;
    for(int i=0; i<N; i++) 
    {
        cin >> arr[i];
        dp[i]=1; //초기 길이는 1
    }

    for(int i=0; i<N; i++)
    {
        for(int j=0; j<i; j++)
        {
            if(arr[i] > arr[j]) dp[i] = max(dp[i], dp[j]+1); //길이 갱신
        }
        result = max(result, dp[i]); //최대값 갱신
    }
    
    cout << result;

    return 0;
}

 

가장 긴 증가하는 부분 수열을 찾는 문제이다.

이런 류의 문제가 제법 있는 편인데, 가장 기본적인 형태의 문제인 것 같다.

 

초기 dp를 1로 갱신하여 초기 길이를 1로 설정해주고, 처음 위치 ~ 현재 위치 (i) 를 탐색하여 현재 위치의 값이 더 클때마다 dp 길이를 갱신해주면 된다.