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

문제:www.acmicpc.net/problem/14002

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

이 문제는 다른 것이 아닌 파이썬 문법에 대한 부족으로 오래 걸렸다.

 

import sys
N = int(sys.stdin.readline().rstrip())
quest = [0]+list(map(int,sys.stdin.readline().rstrip().split()))
dp = [0]*1001
li = []
ans=0
li.append([])
li[0].append(0)
for i in range(1,N+1):
    dp[i]=1
    li.append([])
    ans=max(dp[i],ans)
    
    for j in range(1,i+1):
        if quest[j]<quest[i]:
            if dp[i]<dp[j]+1:
                li[i]=list(li[j])
                dp[i]=dp[j]+1
                ans=max(dp[i],ans)
    li[i].append(quest[i])
del li[0]
for i in range(N):
    if ans==len(li[i]):
        print(ans)
        for j in li[i]:
            print(j,end=' ')
        break

위의 코딩에서 17번 줄을 보면 li[i]=list(li[j]) 이 부분이 있다. 여기서 list를 안해주면 이상하게  li[i].append(quest[i]) 할 때 특정 리스트인 li[i]가 아닌 모든 수열에 동일하게 더해진다. 톱니바퀴 리스트를 쓸 때에는 저런 점을 유의해야겠다.

 

[[0], [10]]
[[0], [10], [10, 20]]
[[0], [10], [10, 20], [10]]
[[0], [10], [10, 20], [10], [10, 20, 30]]
[[0], [10], [10, 20], [10], [10, 20, 30], [10, 20]]
[[0], [10], [10, 20], [10], [10, 20, 30], [10, 20], [10, 20, 30, 50]]

[[0], [10]]
[[0], [10, 20], [10, 20]]
[[0], [10, 20], [10, 20], [10]]
[[0], [10, 20, 30], [10, 20, 30], [10], [10, 20, 30]]
[[0], [10, 20, 30, 20], [10, 20, 30, 20], [10], [10, 20, 30, 20], [10, 20, 30, 20]] 
[[0], [10, 20, 30, 20, 50], [10, 20, 30, 20, 50], [10], [10, 20, 30, 20, 50], [10, 20, 30, 20, 50], [10, 20, 30, 20, 50]]

리스트를 감싸주지 않았을 때에는 다음과 같이 저장이 된다.