흙금이네 블로그

아이디어 #1 이동거리 합이 최소가 되는 위치는 행과 열 번호 각각의 중앙값이므로, 각 번호와 중앙값과의 차를 모두 더한다. 풀이 #1 행과 열을 구분하여 입력 받은 번호들을 정렬한 후 각각의 중앙값을 찾아 계산한다. import sys input = sys.stdin.readline def solution(): N, M = map(int, input().split()) R, C = [], [] for _ in range(M): r, c = map(int, input().split()) R.append(r) C.append(c) R.sort() C.sort() res = 0 mr = R[M//2] mc = C[M//2] if M%2 == 0: mr = (mr+R[M//2-1])//2 mc = (mc+C[..

아이디어 백트래킹으로 현재 포함된 학생들 모두의 친구이면서 번호가 가장 작은 학생을 포함해 나간다. 풀이 import sys input = sys.stdin.readline def solution(): def dfs(idx, u, li, s): nonlocal res if idx >= K: if not res: res = li return if res: return for v in range(u+1, N+1): if visited[v] == 0: if v in s: visited[v] = 1 dfs(idx+1, v, li+[v], s&graph[v]) K, N, F = map(int, input().split()) graph = [set() for _ in range(N+1)] for _ in range..

아이디어 다익스트라로 최소 도로 건설 비용을 구해 나간다. 풀이 import sys from heapq import heappush, heappop input = sys.stdin.readline INF = int(1e7) delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): m, n = map(int, input().split()) board = [tuple(map(int, input().split())) for _ in range(m)] D = [[INF]*n for _ in range(m)] heap = [] if board[0][0] != -1 and board[-1][-1] != -1: heap = [(board[0][0], 0, 0)] whi..