글 읽기 - 후... 쉽지 않습니다.. 14002 파이썬, 게시판 반례는 완료

seungwuk98 2년 전 0

일단 게시판 반례는 다 본 것 같습니다..

로직

1. arr에서 하나씩 빼서 dp[i] = max(dp[:i]) + 1

2. 이때 빼낸 것의 인덱스를 dp2에 저장

3. 다 끝나고 dp2를 통해 역추적

n = int(input())
arr = [*map(int, input().split())]
length = max(arr)+1
dp = [0]*length
dp2 = [-1]*length
for i in arr:
    max_value = max(dp[:i])
    dp2[i] = dp[:i].index(max_value)
    dp[i] = max_value+1
max_value = max(dp)
print(max_value)
idx = dp.index(max_value)
s = []
while idx in arr:
    s.append(idx)
    idx = dp2[idx]
s.reverse()
print(*s)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

후... 쉽지 않습니다.. 14002 파이썬, 게시판 반례는 완료

seungwuk98 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말