BOJ 11568번: 민균이의 계략

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

11568번: 민균이의 계략

가장 긴 증가하는 부분 수열 문제인데, 문제가 처음 접하는 유형이라 어려웠다. 

검색해보니 dp로 푸는 방법과 이진탐색을 이용하는 방법 두 가지가 있던데, 일단 dp로 풀어보았다.

 

dp[i] = num[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이, 1로 초기화

dp[i] = 0~i-1까지 중 num[i]보다 작은 인덱스의 dp값 + 1과 dp[i]중 max값 갱신

import sys
input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split()))
dp = [1]*N #num[i]를 마지막 원소로 가질 때 가장 긴 증가하는 부분 수열의 길이

for i in range(N):
    for j in range(i):
        if (num[i] > num[j]):
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))