14002번 파이썬

 

res=[]
for num in ary:
  if num not in res:
    res.append(num)

처음엔 모든 인덱스를 한번씩 돌아서 중복되지 않게 res에 추가하고 마지막으로 정렬해서 출력했는데 틀렸다고 떴다..

아래 코드는

1부터 n-1번째 인덱스까지 dp를 이용해서 p[i]에 최대 수열의 길이 값을 넣는 코드이다.

최소 수열  길이는 1이기 때문에 모든 값을 1로 초기화하고

i를 1부터 n-1까지 반복해서 i번째까지의 수열 중에서 최대 길이가 되는 수열의 길이를 구해준다.

ex)  {10, 20, 10, 30, 20, 50} 에서 i가 2면 20까지의 수열에서 수열의 길이를 구한다.

p[j]에 +1을 해준 이유는 j번째 인덱스가 i 번째 값보다 작고 이는 최대 수열의 길이에 j다음 i가 포함되는 것이어서 +1을 해준다.

그 다음 최대 길이의 수열을 찾기 위해서 끝에서부터 최대 수열의 길이와 일치하는 idx를 찾아서 res에 추가해준다!(cnt-1을 하는 이유는 i번째 인덱스의 전 인덱스인 j를 찾기 위해서이다)

import sys
input = sys.stdin.readline
n = int(input())
ary=list(map(int,input().split()))
p=[1 for _ in range(n+1)]
res=[]
for i in range(1,n):
  for j in range(i):
    if ary[i] > ary[j]:
      p[i] = max(p[i],p[j]+1)

cnt = max(p)
for idx in range(n-1,-1,-1):
  if p[idx]==cnt:
    res.append(ary[idx])
    cnt-=1

res.reverse()
print(max(p))
print(' '.join(map(str,res)))