[Python]BAEKJOON 14002번 가장 긴 증가하는 부분 수열 4

SeolLab. 2023. 3. 14. 23:26

728x90

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

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

수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이

www.acmicpc.net

DP활용 Sol.

- 솔직히 다른 블로그의 글을 참고했다. dp 활용까진 이해했는데 아래와 같은 이유로 막혔기 때문이다.
필자는 for i in range(0,N,-1): 이라고 썼다가 왜 안되는지 한참 고민했다. 세번째 argument 값이 역순으로 카운트하게 한다고 착각했기 때문이다.

for i in range(N-1, -1, -1):

라고 써줘야 하는데, N-1에서부터 0까지 1만큼 빼주는 연산이 세번째 argument, '-1'로 표현된 것이다.

N = int(input())
lst = list(map(int,input().split()))
dp = [1] * N 
for i in range(N):
    for j in range(i):
        if lst[i] > lst[j]: dp[i] = max(dp[i],dp[j]+1)
M = max(dp)
print(M)
res = [] 
for i in range(N-1, -1, -1):
    if dp[i] == M: 
        res.append(lst[i])
        M -= 1 
res.reverse()
print(*res)