[BOJ][Python] 백준 12015번: 가장 긴 증가하는 수열2

1일 1PS 60일차!

📚 문제

---

골드 2 가장 긴 증가하는 수열2

💡 풀이 과정

---

• 이는 LIS(Longest Increasing Subsequence) 알고리즘으로 이미 널리 알려져있다.
• 해당 알고리즘에 대한 자세한 내용은 나무위키 에 자세히 나와있으니 참고바란다.

📌포인트

---

• DP 는 점화식 문제에 사용되는 것으로만 인식되었다.
  • 하지만 DP 는 전체의 답을 부분의 답으로 작게 쪼개는 방식이다.
  • 해당 문제에서는 순서대로 들어오는 수에 대해서 해당 수를 포함했을 때 증가하는 수열의 크기를 작성한다면 마지막에 모든 수에 대해서 최대 크기를 출력할 수 있다.

💻 코드

---

import bisect

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

for i in range(1, N + 1):
    index = bisect.bisect_left(dp, arr[i])
    if index == len(dp):
        dp.append(arr[i])
    else:
        dp[index] = arr[i]

print(len(dp) - 1)