one Book a Day

강의실 배정문제. 여러번 풀었던 문제. 방을 몇개 가져갈꺼냐? 끝난시간이면 빼고 갈아끼워준다. import sys input = sys.stdin.readline from heapq import heappop, heappush n = int(input()) heap = [] count = 0 for _ in range(n): num, start, end = map(int, input().split()) heappush(heap, [start,end,num]) classroom = [] start, end, num = heappop(heap) heappush(classroom, end) while heap: start, end, num = heappop(heap) if classroom[0]

등차수열로 속도가 증가했을 때 k번째 돌에서 a만큼의 최대 속도를 가질 수 있고 이는 k = a(a+1)/2 를 만족한다. 정리하면 a = sqrt(2 * k + (1/4)) - 1/2 이기 때문에 i번 위치에서 int(sqrt(2 * i)) + 1까지 검사하면 가능한 모든 속도에서의 값을 조사할 수 있다. import sys input = sys.stdin.readline N, M = map(int, input().split()) dp = [[float('inf')] * (int((2 * N)** 0.5) + 2) for _ in range(N + 1)] dp[1][0] = 0 stones = set([int(input()) for _ in range(M)]) for i in range(2, N + 1..

dfs 백트래킹 했는데 dp로 상태인자 주고 하는게 더 나았을지도 import sys input = sys.stdin.readline def dfs(node, energy, key): global min_energy if energy >= min_energy: return if node == N: min_energy = min(min_energy, energy) return if node + 1

풀이 1. 극소점부터 큰값이 나올때마다 그만큼 채워주면서 연산. import sys input = sys.stdin.readline n = int(input()) cnt = 0 stack = [int(input())] max_num = stack[-1] for _ in range(n - 1): num = int(input()) if stack[-1] < num: cnt += num - stack[-1] max_num = max(max_num, num) stack.pop() stack.append(num) cnt += max_num * len(stack) - sum(stack) print(cnt) 풀이2. 분할정복으로 max_idx를 pivot으로 좌우 분할 해 각 구간의 연산값을 더해주며 최상단까지 올라..

쭉 가면서 계속 바꿔주면 된다. 아니면 누적 배열을 만들어 바꾼 횟수를 기록해주며 홀짝 판별해도 되는데 소요가 비슷하기 때문에 그냥 그리디로 계속 바꾸는게 낫다. import sys input = sys.stdin.readline N, M = map(int, input().split()) A = [list(map(int, list(input().rstrip()))) for _ in range(N)] B = [list(map(int, list(input().rstrip()))) for _ in range(N)] cnt = 0 for i in range(N): for j in range(M): if i < N - 2 and j < M - 2: if A[i][j] != B[i][j]: for x in rang..

hash map으로 index 저장해뒀다가 query 들어오면 반환 import sys input = sys.stdin.readline a_idx = {} N, M = map(int, input().split()) A = sorted([int(input()) for _ in range(N)]) for i in range(N): if A[i] not in a_idx: a_idx[A[i]] = i D = [int(input()) for _ in range(M)] for num in D: if num in a_idx: print(a_idx[num]) else: print(-1)

간단한 hash-map import sys input = sys.stdin.readline num_set = {} N = int(input()) A = list(map(int, input().split())) for num in A: num_set[num] = True M = int(input()) Q = list(map(int, input().split())) for num in Q: if num in num_set: print(1) else: print(0)

기본적인 union-find로 무리짓고 대푯값의 갯수를 세는 문제입니다. def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(x, y): x = find(x) y = find(y) if x > y: x, y = y, x parents[y] = x for test in range(1, int(input()) + 1): N, M = map(int, input().split()) parents = {i: i for i in range(1, N + 1)} for i in range(M): a, b = map(int, input().split()) if find(a) != find(b):..

가중치가 있는 단방향 그래프의 왕복 최단거리를 묻는 문제로 정방향, 역방향으로 다익스트라를 그려준 후 합치면 왕복 최단거리를 구할 수 있습니다. (역방향 다익스트라는 돌아오는 경로에 대한 역탐색이기 때문) from heapq import heappop, heappush def dijkstra(graph, start): dp_dists = {i: float('inf') for i in range(1, N + 1)} dp_dists[start] = 0 heap = [] heappush(heap, (0, start)) while heap: cur_dists, cur_node = heappop(heap) for next_node, next_dist in graph[cur_node]: dists = cur_dis..

가중치 간선이 존재하는 2차원 배열의 이동 간 최소 cost를 묻는 문제로 다익스트라를 이용해 풀 수 있습니다. from heapq import heappush, heappop def dijkstra(x, y): heap = [] dists[x][y] = 0 heappush(heap, (0, 0, 0)) while heap: cur_dist, x, y = heappop(heap) for dx, dy in delta: nx, ny = x + dx, y + dy if 0