백준 11053번 가장 긴 증가하는 부분 수열 파이썬

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

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

 

내 답안

 

import sys
input = sys.stdin.readline

N = int(input())

A = list(map(int, input().split()))

dp = [1] * N

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

print(max(dp))

---

Review

 

이 문제는 다이나믹 프로그래밍을 이용하여 풀었다.

점화식 설명은 그림으로 표현하는 게 이해가 더 쉬워 그림으로 표현했다.

 

문제에서 제시한 예제로 프로그램 돌아가는 걸 적었다.

새로운 배열 dp를 정의하자. dp[i]의 정의는 다음과 같다.

dp[i]  :  A[i]를 마지막 값으로 가지는 가장 긴 증가부분수열의 길이

A[i]가 어떤 증가부분수열의 마지막 값이 되기 위해서는 A[i]가 추가되기 전 증가부분수열의 마지막 값이 A[i]보다 작은 값이여야 한다.
따라서 A[i]를 마지막 값으로 가지는 '가장 긴' 증가부분수열의 길이는 A[i]가 추가될 수 있는 증가부분수열 중 가장 긴 수열의 길이에 1을 더한 값이 된다.

A 배열에서 if A[i] > A[j]: 이게 True라면 dp[i] = max(dp[i], dp[j]+1)이다.

즉 A[i] 보다 작은 위치에 있는 것들 중 dp 테이블 값이 제일 큰 값으로 바꿔주면 된다.

사실 점화식 설명하기가 조금 어려운데 그림으로 이해하면 쉽게 이해할 수 있다.

시간 복잡도는 O(N^2) 이다.

 

---

D[i]를 계산하기 위해 A[0] ~ A[i - 1]를 꼭 다 훑어봐야 하는가?

답은 다 훑어보지 않아도 된다.

가장 긴 증가하는 부분 수열2 는 시간 초과가 뜨기 때문에 다른 방법으로 풀어야한다.