사용자 도구

사이트 도구


ps:problems:boj:12738

가장 긴 증가하는 부분 수열 3

ps
링크acmicpc.net/…
출처BOJ
문제 번호12738
문제명가장 긴 증가하는 부분 수열 3
레벨골드 2
분류

LIS

시간복잡도O(nlogn)
인풋사이즈n<=1,000,000
사용한 언어Python
제출기록155552KB / 1040ms
최고기록912ms
해결날짜2021/06/15

풀이

코드

"""Solution code for "BOJ 12738. 가장 긴 증가하는 부분 수열 3".

- Problem link: https://www.acmicpc.net/problem/12738
- Solution link: http://www.teferi.net/ps/problems/boj/12738

Tags: [LIS] [BinarySearch]
"""

import bisect


def main():
    N = int(input())  # pylint: disable=unused-variable
    A = [int(x) for x in input().split()]

    arr = []
    for a_i in A:
        pos = bisect.bisect_left(arr, a_i)
        if pos == len(arr):
            arr.append(a_i)
        else:
            arr[pos] = a_i

    print(len(arr))


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
D J W Q H
 
ps/problems/boj/12738.txt · 마지막으로 수정됨: 2021/06/15 15:43 저자 teferi