one Book a Day

내림차순 정렬 import sys input = sys.stdin.readline for _ in range(int(input())): J, N = map(int, input().split()) cases = [] for i in range(N): R, C = map(int, input().split()) cases.append(R*C) cases.sort(reverse=True) cnt = 0 for case in cases: J -= case cnt += 1 if J

거리가 D이상인 노드들에 대해 거리 측정. max_d는 리프노드로부터의 거리. import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def dfs(cur_node, pre_node): global ans max_d = 0 for next_node in graph[cur_node]: if next_node != pre_node: max_d = max(max_d,dfs(next_node, cur_node)) if max_d >= D: ans += 1 return max_d + 1 N, S, D = map(int, input().split()) graph = {i: [] for i in range(1,N+1)} visited = [0] * (N..

다 구할필요없다. 최소 최대를 만드는 조건만 적용하면 된다. import sys input = sys.stdin.readline minkyum = input().rstrip() n = len(minkyum) max_v = '' left = 0 for i in range(n): if minkyum[i]=='K': max_v += '5' + '0'*(i - left) left = i+1 if minkyum[n-1] =='M': max_v += '1'*(n - left) min_v = '' left = 0 for i in range(n): if minkyum[i]=='K': if i>0 and minkyum[i-1]=='M': min_v += str(10**(i-left-1)) min_v += '5' left..

set으로 중복체크. import sys input = sys.stdin.readline while 1: try: N, M = map(int, input().split()) except: break ans = 0 for num in range(N,M+1): cnt = set() s_num = str(num) for char in s_num: cnt.add(char) if len(s_num) == len(cnt): ans += 1 print(ans)

배열이 두개면 matching으로 풀면된다. A+B = T -> T - A = B import sys input = sys.stdin.readline from collections import defaultdict T = int(input()) n = int(input()) arr_a = list(map(int, input().split())) check = defaultdict(int) for k in range(1, n+1): left = 0 s = 0 for right in range(n): s += arr_a[right] if right - left == k-1: check[T - s] += 1 s -= arr_a[left] left += 1 ans = 0 m = int(input()) arr_b..

처음을 누르고 시작하는 방법과 그렇지 않은 방법 두 가지 중 유효한 최솟값으로 간다. import sys input = sys.stdin.readline def change(now, cnt): if cnt == 1: now[0] ^= 1 now[1] ^= 1 for i in range(1, n-1): if now[i-1] != target[i-1]: cnt += 1 now[i-1] ^= 1 now[i] ^= 1 now[i+1] ^= 1 if now[n-2] != target[n-2]: cnt += 1 now[n-2] ^= 1 now[n-1] ^= 1 return cnt if now == target else float('inf') n = int(input()) now = list(map(int, inpu..

LIS import sys input = sys.stdin.readline from bisect import bisect_left n = int(input()) arr = list(map(int, input().split())) answer = [arr[0]] for num in arr[1:]: if answer[-1] < num: answer.append(num) else: answer[bisect_left(answer,num)] = num print(len(answer))

투포인터 O(n) import sys input = sys.stdin.readline N, M = map(int, input().split()) arr_a = list(map(int, input().split())) arr_b = list(map(int, input().split())) ai = 0 bi = 0 answer = [] while 1: if arr_a[ai]

Parametric Search 최적화 해법인 이분탐색을 결정문제로 바꾸어 푸는 기법. ex.) 고기를 200g잘라라 -> 고기가 200g보다 가벼운가? 무거운가? 의 결정문제로 바꿈.(예 아니오) 특정 값을 찾는게 아닌 오차 범위 내에서 가장 가까운 부등호 식으로 결과를 판별한다. 가능한 해의 영역이 연속적이어야 한다. (최솟값 결정문제 a가 만족한다면 a이상의 값은 모두 만족.) 예제 BOJ 1637 날카로운 눈 import sys input = sys.stdin.readline def get_sum(target): total = 0 for i in range(N): if target >= arr[i][0]: total += ((min(arr[i][1],target) - arr[i][0])//arr[..

적 / 부. target이하의 값들의 합이 홀수냐? 짝수냐? import sys input = sys.stdin.readline def get_sum(target): total = 0 for i in range(N): if target >= arr[i][0]: total += ((min(arr[i][1],target) - arr[i][0])//arr[i][2]) + 1 return total N = int(input()) arr = [list(map(int, input().split())) for _ in range(N)] left = 0 right = 2147483648 while left < right: mid = (left + right)//2 if not get_sum(mid)&1: left = ..