문제

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

나의 코드 (답안 참조)

"""
1. 아이디어
LIS(Longest Increasing Subsequence) 라는 유명한 DP 문제라고 한다..
dp 리스트에 자신을 포함하여 만들수 있는 부분 수열 크기를 저장해야한다.

2. 시간복잡도
O(N * N-1 * 2) 이정도?
"""

from sys import stdin
input = stdin.readline

n = int(input())
seq = list(map(int, input().split()))
dp = [1] * n # 1로 초기화 한 이유는 숫자 자신이 1부터 시작하기 떄문이다.

for i in range(n):
    for j in range(i):
        if seq[j] < seq[i]: # 만약 현재 숫자가 이전 숫자 보다 큰 지점을 만난다면
            dp[i] = max(dp[i], dp[j]+1) # 현재 dp와 이전 숫자에 +1한 dp중 큰 것을 택한다.

print(max(dp))
    

느낀점

이거 좀 어려운거 같았는데 코드보니 쉬운거 같다. 근데 이거 처음 풀면 생각하기 좀 어렵고 DP 많이 풀다보면 바로 생각날 것 같은 문제이다.

위의 주석을 보고도 코드가 헷갈리면 밑에 껄 참조하자.

seq	10	20	10	30	20	50
DP	1	2	1	3	2	4