흙금이네 블로그

아이디어 #1 플로이드-워셜을 이용하여 지역 간 최소 거리를 갱신하고, 획득할 수 있는 최대 아이템 수를 계산한다. 풀이 #1 import sys input = sys.stdin.readline def solution(): n, m, r = map(int, input().split()) T = [0]+list(map(int, input().split())) D = [[150000]*(n+1) for _ in range(n+1)] for _ in range(r): a, b, l = map(int, input().split()) D[a][b] = l D[b][a] = l for k in range(1, n+1): D[k][k] = 0 for i in range(1, n): for j in range(i+1,..

아이디어 중간에 있는 충전소들의 거리가 모두 200 이하이고, 델타 정션까지 왕복할 수 있는지 확인한다. 풀이 import sys input = sys.stdin.readline while n := int(input()): if n 200: print('IMPOSSIBLE') break elif stations[i+1]+100 >= 1422: print('POSSIBLE') break else: print('IMPOS..

아이디어 격자에 중력과 회전을 적용하며 BFS로 블록 그룹을 찾아 점수 합을 계산한다. 풀이 import sys input = sys.stdin.readline def solution(): delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def gravity(): for c in range(N): end = N-1 for r in range(N-1, -1, -1): if board[r][c] >= 0: board[end][c] = board[r][c] if end != r: board[r][c] = -2 end -= 1 elif board[r][c] == -1: end = r-1 def rotate(): nonlocal board board = list(map(list, zi..

아이디어 연료가 남은 동안 손님들을 이동시키며 모든 손님을 이동시켰을 때 남은 연료를 출력한다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): N, M, K = map(int, input().split()) board = [list(map(lambda x: -int(x), input().split())) for _ in range(N)] des = dict() r, c = map(int, input().split()) queue = [(r-1, c-1)] for i in range(1, M+1): s_r, s_c, e_r, e_c = map(lambda x: int(x)-1..

아이디어 조건에 따라 상어를 이동하고 상어가 한 마리만 남는 데 걸리는 시간을 출력한다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (1, 0), (0, -1), (0, 1)] def solution(): N, M, k = map(int, input().split()) board = [] sharks = [[] for _ in range(M+1)] for r in range(N): board.append([]) temp = tuple(map(int, input().split())) for c in range(N): board[-1].append([temp[c], temp[c], 0]) if temp[c]: sharks[temp[c]] = [r..

아이디어 깊은 복사로 공간 정보를 넘기며 DFS로 상어가 먹을 수 있는 물고기 번호의 합의 최댓값을 구한다. 풀이 delta = [(-1, 0), (-1, -1), (0, -1), (1, -1), (1, 0), (1, 1), (0, 1), (-1, 1)] def dfs(fish, board, total): global res for i in range(1, 17): if fish[i]: r, c, d = fish[i] dr, dc = delta[d] nr, nc = r+dr, c+dc while 1: if 4 > nr >= 0 and 4 > nc >= 0 and board[nr][nc] != -1: board[r][c], board[nr][nc] = board[nr][nc], i if fish[board..

아이디어 상자 넓이를 기준으로 상자들을 내림차순 정렬한 후, 차례로 사탕 개수에서 상자 넓이 값을 뺀다. 풀이 import sys input = sys.stdin.readline def solution(): T = int(input()) for t in range(T): J, N = map(int, input().split()) boxes = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x: -x[0]*x[1]) res = 0 for R, C in boxes: J -= R*C res += 1 if J

아이디어 조건에 따라 블록을 처리하는 보드를 구현하되, 블록을 쉽게 처리하기 위해 파란색 보드는 전치하여 구현한다. 풀이 import sys input = sys.stdin.readline def solution(): N = int(input()) green = [[0]*4 for _ in range(6)] blue = [[0]*4 for _ in range(6)] score = cnt = 0 for _ in range(N): t, x, y = map(int, input().split()) if t == 1: cnt += 2 for r in range(2, 6): if green[r][y]: green[r-1][y] = 1 break else: green[5][y] = 1 for c in range(2,..

아이디어 조건에 따라 말을 이동시키며 이동한 칸의 말 개수가 4개 이상인 경우 해당 턴을 출력한다. 풀이 import sys input = sys.stdin.readline delta = [(0, 1), (0, -1), (-1, 0), (1, 0)] def solution(): def reverse(idx): bottom = idx while idx != -1: bottom = idx pieces[idx][3], pieces[idx][4] = pieces[idx][4], pieces[idx][3] idx = pieces[idx][4] return bottom def move(color): top, bottom = board[r][c], i board[r][c] = pieces[i][4] if pieces..

아이디어 각 칸에서 이동할 수 있는 칸에 대한 정보를 저장한 후, 현재 턴에서 이동하지 않은 칸으로 이동하며 최대 점수를 구한다. 풀이 board = [ (0, 1, 2, 3, 4, 5), (2, 2, 3, 4, 5, 6), (4, 3, 4, 5, 6, 7), (6, 4, 5, 6, 7, 8), (8, 5, 6, 7, 8, 9), (10, 21, 22, 23, 29, 30), (12, 7, 8, 9, 10, 11), (14, 8, 9, 10, 11, 12), (16, 9, 10, 11, 12, 13), (18, 10, 11, 12, 13, 14), (20, 24, 25, 29, 30, 31), (22, 12, 13, 14, 15, 16), (24, 13, 14, 15, 16, 17), (26, 14, 1..