[DP] 11053번 가장 긴 증가하는 부분수열

"이것이 코딩테스트다(나동빈 저)"에서 나온 문제에 대한 코드를 다루고 있습니다.
문제에 대한 구체적인 설명과 조건 등은 책을 참고해주시기 바랍니다.

소요시간: 10분 + a

1. 문제 설명

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

11053번: 가장 긴 증가하는 부분 수열

2. 접근 방식

- 점화식: 모든 0 <= j < i에 대해, DP[i] = max(DP[i], DP[j] + 1) if array[j] < array[i]

3. 코드

n = int(input())
ls = list(map(int, input().split()))

dp = [1]*n
for i in range(1, n):
    for j in range(0, i):
        if ls[j] < ls[i]: # 핵심 코드
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

4. 코멘트

- 해당 문제는 이전에 한 번 풀었던 문제여서 수월하게 풀었다. 값이 1인 dp를 설정해주는 부분과 , i에 대해서 모든 j를 확인하는 부분을 이해하면 풀 수 있다. 

- 다른 DP와는 다르게 n의 크기가 크지 않기 때문에, 이중 for문으로 dp를 만들어서 문제를 풀 수 있다.