글 읽기 - (파이썬) 이 풀이가 왜 맞는지 모르겠습니다.

pkj6962 1년 전 0

다른 분들의 풀이를 참고하던 중 왜 맞는지 이해가 안되는 코드가 있어서 질문드립니다.

이 풀이는 dp를 부분수열 그 자체로 정의하고 푼 풀이로 보이는데요.

이 풀이대로면

10 25 30 24

와 같은 입력이 주어졌을 때 최종적으로 답이 되는 부분수열은 10 24 30 이 됩니다. (길이는 같지만요)

이 풀이가 왜 맞는 풀이인지 궁금합니다.

N = int(input())
li = list(map(int,input().split()))
dp = [li[0]]

for i in range(1,N):
    if li[i] > dp[-1]:
        dp.append(li[i])
    else:
        j = len(dp)-1
        while j > 0:
            if dp[j-1] < li[i]:
                break
            j -= 1
        dp[j] = li[i]
print(len(dp))

msphere 1년 전 0

해당 풀이는 dp 배열의 길이가 LIS의 길이가 되지만, dp 배열에 있는 값이 LIS가 되는 것은 아닙니다.

이분탐색을 이용하는 O(NlogN) LIS를 공부해보시면 좋을 것 같네요.

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

문제

문제

출처

ICPC

(파이썬) 이 풀이가 왜 맞는지 모르겠습니다.

pkj6962 1년 전 0

msphere 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말