글 읽기 - 접근법, 반례 질문

bitlez3470 2년 전 0

dp 는 실제 증가하는 수열을 추적하고 있는 변수이고 temp 는 나중에 각각의 인덱스에서 더 작은 값들을 담고 있는 변수입니다.

temp에 바이너리 서치로 인덱스를 업데이트해주다가 새로 들어올 수가 temp의 경우 추가되지만 dp 의 경우 추가되지 못할 경우 temp 를 dp 로 옮긴다고 판단했습니다.

접근에 오류나 반례를 들어주시면 감사하겠습니다.

from bisect import bisect_left
import sys 
input = sys.stdin.readline

n = int(input())
lst = list(map(int, input().split()))

dp = []
temp = []

for i in lst:
    k = bisect_left(temp, i)
    if k >= len(temp):
        s = bisect_left(dp, i)
        if k == s:
            dp.append(i)
            temp.append(i)
        else:
            temp.append(i)
            dp = temp[:]
    else:
        temp[k] = i

print(len(dp))
print(' '.join(map(str, dp)))

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

문제

문제

출처

ICPC

접근법, 반례 질문

bitlez3470 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말