🥚문제

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

• 다이나믹 프로그래밍

🥚입력/출력

🍳코드

import sys
import bisect
input = sys.stdin.readline

n = int(input())
arr = [0] + list(map(int, input().split()))

# LIS = O(NlogN)
# dp[i] = 길이가 i인 증가하는 부분 수열의 마지막 숫자의 최소값

def LIS():
    dp = [0]
    for i in range(1, n+1):
        if arr[i] > dp[-1]:
            dp.append(arr[i])
        else:
            idx = bisect.bisect_left(dp, arr[i])  # 이분탐색으로 들어갈 자리 찾기
            dp[idx] = arr[i]
    return len(dp) - 1

ans = LIS()
print(ans)

🧂아이디어

DP, LIS

• 최장 증가 부분 수열의 알고리즘을 이용하여 푼다.
  이전에 관련 문제들을 몇 번 풀었는데, O(NlogN)의 시간복잡도를 가지는 알고리즘을 구현하는 데 좀 실수가 있었던 것 같다. 오늘 풀면서 문득 어 이거 아닌데? 하는 생각 들어서 수정했다 ㅎㅎ...

• dp[i] = 길이가 i인 증가하는 부분 수열에서 마지막 숫자가 될 수 있는 최소값을 저장한다.

• 박스의 크기가 저장되어있는 리스트 arr을 순회하면서, arr[i]가 dp의 마지막 값보다 크다면 dp에 arr[i]를 추가한다.

• arr[i]가 dp의 마지막 값보다 작다면, arr[i]가 들어갈 수 있는 인덱스를 이분탐색을 통해 찾은 뒤, dp[idx] = arr[i]로 업데이트한다.

• 이분탐색은 파이썬 bisect모듈의 bisect_left함수를 사용한다.
  이렇게 입력 N개에 대해 ✨이분탐색✨을 시행하기 때문에 시간복잡도가 O(NlogN)!

참고 1: LIS 코드 및 설명
참고 2: 가장 긴 바이토닉 부분 수열
참고 3: 가장 긴 감소하는 부분 수열
참고 4: 가장 긴 증가하는 부분 수열 4