풀캠정글러

from bisect import bisect_left n = int(input()) l = list(map(int, input().split())) table = [l[0]] for i in range(1, n): if l[i] > table[-1]: table.append(l[i]) else: table[bisect_left(table, l[i])] = l[i] print(len(table)) 수열의 원소의 range는 +-10억으로 넓어졌지만, 수열의 길이는 12015와 마찬가지로 1,000,000이다 이분탐색을 이용한 대소비교에는 문제가 없으므로 12015와 같은 코드(https://uneducatedjungler.tistory.com/47)로도 시간 안에 제출할 수 있다.

from bisect import bisect_left n = int(input()) l = list(map(int, input().split())) table = [l[0]] for i in range(1, n): if l[i] > table[-1]: table.append(l[i]) else: table[bisect_left(table, l[i])] = l[i] print(len(table)) 11053과 같은 문제이지만, 에 비해 range가 커졌다. 즉, 11053의 코드(https://uneducatedjungler.tistory.com/45)처럼 원소 하나하나에 대해 자기보다 이전 index의 원소를 for문으로 뒤져가며 자기가 들어갈 위치를 찾기엔 시간이 부족하다. 단순탐색으론 안되니 이분탐..

n = int(input()) l = list(map(int, input().split())) order = [0 for i in range(n)] for after in range(n) : for before in range(after) : if l[after] < l[before] and order[after] < order[before] : order[after] = order[before] order[after] = order[after] + 1 print(max(order)) 11053의 코드(https://uneducatedjungler.tistory.com/45)에서 부호만 바꾸면 된다. 이런식으로 약간씩 디테일이 다른 연관문제가 많이 있던데 하나하나 정리해봐야겠다.

n = int(input()) l = list(map(int, input().split())) order = [0 for i in range(n)] for after in range(n) : for before in range(after) : if l[after] > l[before] and order[after] < order[before] : order[after] = order[before] order[after] = order[after] + 1 print(max(order)) 길이 n의 0으로 된 order 테이블을 만든다. 리스트의 모든 원소에 대해, 자기보다 이전 index이면서 값이 작은 원소를 탐색한다. 그 원소의 order가 현재 자신의 order보다 크다면, 자신의 order를 그 값..

import sys input = sys.stdin.readline n, c = map(int, input().split()) l = [] for i in range(n) : l.append(int(input())) l.sort() def Bsearch(list) : drangel = 1 dranger = list[-1] - list[0] while drangel = d : now = list[i] count = count + 1 if count >= c : maxd = d drangel = d + 1 else : dranger = d - 1 return maxd print(Bsearch(l)) 집들의 위치를 리스트에 받아서 정렬했을 때, 정답 d는 양 끝 두 집의 거리보다 클 수 없다. 1

import sys input = sys.stdin.readline import heapq n = int(input()) ll = [] for i in range(n) : a, b = map(int, input().split()) ll.append([min(a, b), max(a, b)]) d = int(input()) l = [] for li in ll : if li[1] - li[0]

import sys input = sys.stdin.readline import heapq n = int(input()) l = [] sum = 0 for i in range(n) : c = int(input()) heapq.heappush(l, c) for i in range(n-1) : a = heapq.heappop(l) b = heapq.heappop(l) sum = sum + a + b heapq.heappush(l, a + b) print(sum) a와 b를 합친 덱을 또다른 덱 c와 정렬할 때는 a와 b가 모두 카운트된다. 즉 매수가 많은 덱은 가능한 한 늦게 합쳐야 덜 카운트되고, 이는 항상 가장 적은 둘을 합쳐야 함을 의미한다. 받은 리스트를 힙의 형태로 정리하여 2번의 pop으로 최솟값..

import sys input = sys.stdin.readline import heapq under = [] over = [] n = int(input()) for i in range(n) : x = int(input()) if len(under) == len(over) : heapq.heappush(under, -x) else : heapq.heappush(over, x) if over != [] and -under[0] > over[0] : a = -heapq.heappop(under) b = heapq.heappop(over) heapq.heappush(under, -b) heapq.heappush(over, a) print(-under[0]) heap의 구현은 이전 문제에서 해봤으니 생략하고 h..

import sys input = sys.stdin.readline heap = [''] n = int(input()) for i in range(n) : e = int(input()) if e == 0 : if heap == [''] : print(0) else : e = heap[-1] heap[1], heap[-1] = heap[-1], heap[1] print(heap[-1]) del heap[-1] index = 1 while index * 2 = heap[b] : next = a else : next = b if e < ..

n = int(input()) apple = [] k = int(input()) for i in range(k) : y, x = map(int, input().split()) apple.append([y, x]) order = [] l = int(input()) for i in range(l) : X, C = input().split() order.append([int(X), C]) right = [0, 1] # down = [1, 0] # left = [0, -1] # up = [-1, 0] def drift(d, lr) : if lr == 'D' : return [d[1], -d[0]] if lr == 'L' : return [-d[1], d[0]] snake = [[1,1]] direction = ..