백준 12015 [가장 긴 증가하는 부분 수열 2] 파이썬

https://www.acmicpc.net/problem/12015

 

#백준 12015 가장 긴 증가하는 부분 수열 2
from collections import defaultdict
N=int(input())
arr=list(map(int,input().split()))

dp=[0 for _ in range(N+1)]
dp[0]=1
dic=defaultdict()
dic[arr[0]]=1
is_changed=False
for i in range(1,N):
    for val in dic:
        if val<arr[i]:
            dp[i]=max(dp[i],dic[val])
            is_changed=True
    if is_changed:
        dp[i]+=1
        dic[arr[i]]=dp[i]
        is_changed=False
    else:
        dp[i]=1
        dic[arr[i]]=1
print(max(dp))

O(N^2) 복잡도로 해결하려고 하였는데 실패하였다. 이 문제는 이분탐색을 이용하여야만 풀 수 있는 문제였다.

 

결국 해결하지 못해서, GPT의 도움을 받았다.

 

#백준 12015 가장 긴 증가하는 부분 수열 2
import sys
from bisect import bisect_left

# 입력 받기
N = int(sys.stdin.readline())
arr = list(map(int, sys.stdin.readline().split()))

# tails 리스트 초기화
# tails[k]는 길이가 k+1인 증가 부분 수열의 가장 작은 마지막 원소를 저장합니다.
tails = []

for num in arr:
    # bisect_left를 사용하여 num이 tails에 들어갈 적절한 위치(인덱스)를 찾습니다.
    # 이 위치는 num보다 크거나 같은 첫 번째 원소의 인덱스입니다.
    idx = bisect_left(tails, num)

    if idx == len(tails):
        # 만약 idx가 tails의 길이와 같다면,
        # 이는 num이 tails의 모든 원소보다 크다는 의미입니다.
        # 따라서 num은 기존의 가장 긴 증가 부분 수열보다 더 긴 수열을 만듭니다.
        # num을 tails의 끝에 추가합니다.
        tails.append(num)
    else:
        # 그렇지 않다면, num은 tails[idx]의 위치에 들어갈 수 있습니다.
        # 이는 길이가 (idx + 1)인 증가 부분 수열을 만들 수 있음을 의미하며,
        # tails[idx]를 num으로 교체함으로써 같은 길이의 수열 중
        # 더 작은 마지막 원소를 가지는 '더 좋은' 수열을 만들 수 있습니다.
        # 이렇게 되면 나중에 오는 숫자들은 이 더 작은 마지막 원소에 더 쉽게 연결될 수 있습니다.
        tails[idx] = num

# tails 리스트의 길이가 최장 증가 부분 수열의 길이입니다.
print(len(tails))

갈 길이 멀다..