코테분석#9-2 가장 긴 증가하는 부분 수열 4 (11055번)

1. 문제

2. 나의 풀이

3-1. 쌤's 풀이

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

# DP[i] : i까지 왔을 때, 합의 최대
DP = copy.deepcopy(A)

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

• 시간복잡도는 N**2
• N이 1000보다 작을때 가능한 풀이

3-2. 쌤's 풀이

• 간장 긴 증가하는 부분 수열의 경로를 출력한다라고 문제를 추가하면..!
• 경로를 추적하는 문제는 어려운 문제..! 보통 카카오에서 종종 나옴

import copy

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

# DP[i] : i까지 왔을 때, 합의 최대
DP = copy.deepcopy(A)
rev = [i for i in range(N)]

idx = 0

for i in range(1, N):
    for j in range(i):
        if A[i] > A[j] and DP[i] < (A[i] + DP[j]):
            DP[i] = DP[j] + DP[j]
            rev[i] = j
    if DP[idx] < DP[i]:
        idx = i

print(DP[idx])
while rev[idx] != idx:
    print(A[idx], sep = " ")
    idx = rev[idx]

print(A[idx])

4. 느낀 점