[실버 2] 백준 11053 - 가장 긴 증가하는 부분 수열 (파이썬)

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

풀이

이 문제는 조금 복잡하다… 일단 다이나믹 프로그래밍 풀이로 작성하였는데, 일반적인 풀이보다 2차원 DP를 활용한 조금은 특이한 방식이다.

일단 문제는 수열 A가 주어졌을때, 증가하는 부분 수열 중 가장 길이가 긴 것의 길이를 구하는 문제이다.

D = [[0] * 1001 for _ in range(N)] # N * 1001

D[i][j] 는 i번째까지 고려했을때, 마지막 수가 j이하인 증가 부분 수열의 최대 길이이다.

for i in range(1001):
    D[0][i] = 1 if A[0] <= i else 0

첫번째 원소만 쓸 수 있는 상황에서 j 조건을 만족하면 길이는 1로 지정한다.

for i in range(1, N):
    for j in range(1001):
        D[i][j] = D[i - 1][j]  # 이전까지의 최대값 유지
 
        if A[i] <= j:
            D[i][j] = max(D[i][j], 1 + D[i - 1][A[i] - 1])

점화식을 구성하면 D[i][j] = D[i - 1][j] 즉 i 번째 숫자를 사용하지 않고 이전 상태를 그대로 유지한다.

if A[i] ≤ j 는 j를 마지막 원소로 가지는 증가 수열에 A[i]를 넣을 수 있는 경우이다. 이떄 A[i]를 새로운 마지막 숫자로 선택한 것이므로, 그 전에 A[i] - 1 이하로 끝나는 수열의 최대 길이에서 +1을 해준다.

시간 복잡도 분석

O(N * 1000) → 충분히 시간이 널널하다.

코드

# 백준 11053 - 가장 큰 증가하는 부분 수열
# 분류 - 다이나믹 프로그래밍
 
N = int(input())
A = list(map(int, input().split()))
 
D = [[0] * 1001 for _ in range(N)] # N * 1001
 
for i in range(1001) :
    D[0][i] = 1 if A[0] <= i else 0
 
for i in range(1, N) :
    for j in range(1001) :
        D[i][j] = D[i - 1][j]
 
        if A[i] <= j :
            D[i][j] = max(D[i][j], 1 + D[i - 1][A[i] - 1])
 
print(D[N - 1][1000])