백준 문제풀이(파이썬)/이분 탐색

두 번째 LIS 문제이다. 이전에 풀었던 문제와 같지만 범위가 1000에서 1000000으로 늘어났기 때문에 O(N²) 풀이법인 dp로 풀면 시간 초과가 나올게 분명하다. O(NlogN) 풀이의 핵심은 LIS를 구하는 것이 아니라 LIS의 길이만 구하는 것이다. 단지 길이만 구하는 것이기 때문에, 순회하면서 저장해둔 배열의 마지막 원소보다 크면 append해주고 작으면 덮어주는(?) 식으로 풀면 된다. ##함수 선언 부분 import sys input = sys.stdin.readline ##변수 선언 부분 A = [] dp = [0] mid = 0 ##메인 함수 부분 if __name__ == "__main__": N = int(input()) A = [int(x) for x in input().spl..

놀랍게도 이분 탐색으로 풀리는 문제이다. B[k]는 어찌됐건 1부터 N²까지 수 중에 하나이기 때문에, 1을 left, N²을 right로 설정하여 이분 탐색을 진행하면 될 것이다. k가 의미하는 것이 무엇일까? N = 5이고, k = 16인 경우를 생각해보자. N = 5인 경우를 쭉 나열해보면, B[k] = B[16] = 10이다. 10과 N과 k의 관계에 대해 알아내면 대충 감이 올 것 같다. B = [1, 2, 2, 3, 3, 4, 4, 4, 5, 5, 6, 6, 8, 8, 9, 10(k), 10, 12, 12, 15, 15, 16, 20, 20, 25] k번째 이전의 숫자들은 2차원 배열일 때 [1][1] ~ [1][5] : 5개 [2][1] ~ [2][5] : 5개 [3][1] ~ [3][3] ..