one Book a Day

최소 이동거리 문제로 인접리스트가 주어져 다익스트라로 풀이했습니다. from heapq import heappush, heappop def dijkstra(start): heap = [] dists[start] = 0 heappush(heap, (0, start)) while heap: cur_dist, cur_node = heappop(heap) for next_node, next_dist in graph[cur_node]: dist = cur_dist + next_dist if dists[next_node] > dist: dists[next_node] = dist heappush(heap, (dist, next_node)) for test in range(1, int(input()) + 1): N, ..

가중치가 있는 2차원 배열의 최소거리를 구하는 문제로 다익스트라를 사용했씁니다. 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

기본적인 MST 문제로 간선이 주어졌기 때문에 크루스칼 알고리즘을 사용해 풀이했습니다. from heapq import heappop, heappush def find(x): if parents[x] == x: return x parents[x] = find(parents[x]) return parents[x] def union(a, b): a = find(a) b = find(b) if a > b: a, b = b, a parents[b] = a for test in range(1, int(input()) + 1): V, E = map(int, input().split()) parents = {i: i for i in range(V + 1)} edges = [] for __ in range(E): a,..

보자마자 price(1~count) 가 생각나서 제출. 했으나 제출 누르자마자 음수인 경우 예외처리 안해줬다는 생각이 나서 결과보니 아니나다를까 testcase 하나 오답.. 음수처리 해주었더니 통과 def solution(price, money, count): answer = price * count * (count + 1) // 2 - money if answer < 0: answer = 0 return answer

중앙값 계속 체크해서 반환. 슬라이딩 윈도우처럼 돌리는건 불가능할까? 사실 세로로 삽입하면 한줄씩은 3개씩 빼고 넣는게 가능할지도? import sys input = sys.stdin.readline def check_mid(x, y): tmp = [] for i in range(x, x + 3): for j in range(y, y + 3): if tmp: if tmp[-1] = T: return True return False R, C = map(int, input().split()) filters = [list(map(int, input().split())) for __ in range(R)] T = int(input()) cnt = 0 for i in range(R - 2): for j in ra..

2진수는 1 shifting으로 비트체크 후 경우의 수를 후보군 set에 넣어두었고 3진수는 k를 인덱스의 역방향으로 설정하여 연산한 숫자가 후보군 안에 있는지 확인했습니다. for test in range(1, int(input()) + 1): binary, tri = input(), input() init_binary, init_tri = int(binary, 2), int(tri, 3) target_candidate = set() for i in range(len(binary)): if init_binary & (1

set으로 정답이 될수있는 경우를 찾아주면 됩니다. 사실 16칸밖에 되지 않으므로 16자리 bit를 인자로 넘겨주거나 3차원 배열(x, y, bit상태)을 만들어 bit상태와 현재num이 같으면 더 조사하지 않게 가지치기를 할 수 있습니다. 근데 안해도 통과되긴 합니다. def dfs(cnt, x, y, num): global answers if cnt == 7: answers.add(num) return for dx, dy in delta: nx, ny = x + dx, y + dy if 0

문제 이름대로 쉬운 거스름돈 문제입니다. 기본적인 그리디문제입니다. for test in range(1, int(input()) + 1): N = int(input()) units = [50000, 10000, 5000, 1000, 500, 100, 50, 10] unit_cnt = [0] * 8 for i in range(8): if N >= units[i]: cnt = N // units[i] unit_cnt[i] += cnt N %= units[i] print(f'#{test}') print(*unit_cnt)

적힌 숫자가 중복 없이 1씩 늘어나기 때문에 배열에 index로 쓸 수 있습니다. 그 후 index에 따라 이동 가능여부를 조사해주면 됩니다. 올해 하반기 라인 코테 3번 문제와 아이디어가 비슷합니다. for test in range(1, int(input()) + 1): N = int(input()) dp = [0] * (N ** 2 + 1) for i in range(N): row = list(map(int, input().split())) for j in range(N): dp[row[j]] = (i, j) delta = ((0, 1), (1, 0), (0, -1), (-1, 0)) max_length, cnt, start, answer = 1, 1, 1, 1 for num in range(1, l..

dfs로 백트래킹하며 최솟값을 갱신해주는 로직입니다. 높이가 '이상' 임이 명확히 주어져있어서 수월했습니다. def dfs(u, total): global min_val if total >= B: min_val = min(min_val, total) for v in range(u + 1, N): if not visited[v] and total + s[v] < min_val: visited[v] = True dfs(v, total + s[v]) visited[v] = False for test in range(1, int(input()) + 1): N, B = map(int, input().split()) s = list(map(int, input().split())) visited = [False] *..