[백준 12015 파이썬] 가장 긴 증가하는 부분 수열 2 (골드2, 이분탐색)

알고리즘 유형 : 이분탐색
풀이 없이 스스로 풀었나요? : ❌

---

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

솔루션

수열 A를 처음부터 끝까지 for를 돌면서 현재 원소와 res에 있는 마지막 값과 비교하여 더 크면 res에 추가하고 아니면 이분 탐색을 통해 현재 원사가 들어갈 인덱스를 찾는다.

소스 코드

import sys

input = sys.stdin.readline

if __name__ == "__main__":
    n = int(input())
    arr = list(map(int, input().split()))
    res = [0] # 초기값 설정 안하면 res[-1]에서 인덱스 오류 발생

    for a in arr:
        if res[-1] < a:
            res.append(a)
        else:
            lt, rt = 1, len(res)
            while lt < rt:
                mid = (lt + rt) // 2
                if res[mid] < a:
                    lt = mid + 1
                else:
                    rt = mid
            res[rt] = a

    print(len(res) - 1)

---

후기

lt, rt를 어떻게 잡아야하는지 아직 감이 오지 않는다.
좀 더 연습이 필요한거 같다.