one Book a Day

요번엔 defaultdict로. import sys input = sys.stdin.readline from heapq import heappush,heappop from collections import defaultdict for test in range(int(input())): k = int(input()) check = defaultdict(int) max_heap=[] min_heap=[] for i in range(k): command,n = input().split() n=int(n) if command=='D': if n==1: while max_heap and not check[-max_heap[0]]: heappop(max_heap) if max_heap: check[-max_heap..

출발지가 여러개인 bfs. 좌표 먼저 넣어주면 ez // 보통 조합의 부분합 구할때도 많이쓰인다. import sys input = sys.stdin.readline from collections import deque def bfs(): queue = deque() dx = [1, -1, 0, 0] dy = [0, 0, -1, 1] for i in range(N): for j in range(M): if matrix[i][j] == 1: queue.append([i, j]) while queue: x, y = queue.popleft() for i in range(4): nx = x + dx[i] ny = y + dy[i] if 0

XOR연산 import sys input = sys.stdin.readline N = int(input()) switches = list(map(int, input().split())) M = int(input()) for _ in range(M): a, b = map(int, input().split()) # 남학생이면 스위치 번호가 받은 수의 배수이면 그 스위치의 상태를 바꾼다. XOR(3을 받으면 3,6끔) # 여학생은 자기가 받은 스위치 번호를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아 상태를 모두 바꾼다. XOR if a==1: for i in range(N): if not (i+1)%b: switches[i] ^= 1 else: size=1 while b-1-size>..

분할정복쓰 import sys input = sys.stdin.readline def check(x,y,size): color = matrix[x][y] for i in range(x,x+size): for j in range(y,y+size): if not color==matrix[i][j]: return False if color==1: answer[1] += 1 else: answer[0] += 1 return True def divide_paper(start_x,start_y,length): if not check(start_x,start_y,length//2): divide_paper(start_x,start_y,length//2) if not check(start_x+length//2,star..

핵심은 이미 푼 문제를 각 힙에서 제거하는 매커니즘. import sys input = sys.stdin.readline from heapq import heappop,heappush from collections import defaultdict N = int(input()) min_heap = [] max_heap = [] in_list = defaultdict(bool) for _ in range(N): P, L = map(int, input().split()) heappush(min_heap,[L,P]) heappush(max_heap,[-L,-P]) in_list[P] = True M = int(input()) for _ in range(M): command = input().split() if..

시간정보에 대한 전처리가 귀찮은 문제. 저게 최선인가 싶긴 하다. 나머지로직은 강의실 배정, 방배정 문제와 동일. import sys input = sys.stdin.readline from heapq import heappush, heappop N = int(input()) buses = [] for _ in range(N): arrive, leave = input().split() a = int(''.join((''.join(arrive.split(':'))).split('.'))) b = int(''.join((''.join(leave.split(':'))).split('.'))) buses.append([a,b]) buses.sort() heap = [] heappush(heap,buses[0][..

하나씩 때리면 시간초과고 마왕이 끔살나는 기준에 따라 죽는 회차가 다르니 그거만 계산해서 용사 죽는 회차랑 비교해주면 된다. import sys input = sys.stdin.readline from math import ceil h_hp, h_atk, d_hp, d_atk = map(int, input().split()) P, S = map(int, input().split()) # h_hp d_atk로 나눈 몫 올림값이 용사 사망 cnt h_death_cnt = ceil(h_hp/d_atk) # d_hp - P 를 h_atk로 때린 나머지에 P를 더한 값이 h_atk보다 작을경우 d_hp - P를 h_atk로 나눈 몫+1에 끔살 if (d_hp-P)%h_atk and (d_hp-P)%h_atk + ..

그냥 D규칙에따라 거꾸로 보내면 된다. import sys input = sys.stdin.readline N, K = map(int, input().split()) after_shuffle = list(map(int, input().split())) D = list(map(int, input().split())) for _ in range(K): tmp = [0]*N for i in range(N): tmp[D[i]-1] = after_shuffle[i] after_shuffle = tmp print(*after_shuffle)

얘는 늘 dfs.. import sys input = sys.stdin.readline def dfs(expression, depth, use_cnt): global max_result, min_result if depth == N: tmp = eval(expression) max_result = max(max_result, tmp) min_result = min(min_result, tmp) return if use_cnt[0] < p_cnt: use_cnt[0] += 1 dfs(expression + "+" + str(nums[depth]), depth + 1, use_cnt) use_cnt[0] -= 1 if use_cnt[1] < mi_cnt: use_cnt[1] += 1 dfs(expressio..

이분탐색으로 무게중심 찾고 그 좌우에 있는 마을만 거리비교해서 최솟값으로 가져감. 둘 거리같으면 왼쪽꺼 가져감. import sys input = sys.stdin.readline from bisect import bisect_left def cal_dist(position): dist = 0 for town, population in arr: dist += abs(position-town)*population return dist N = int(input()) arr = [tuple(map(int, input().split())) for _ in range(N)] left = -1000000000 right = 1000000000 answer = 0 while left