흙금이네 블로그

아이디어 CCW(Counter Clock Wise)로 각 선분의 두 점과 다른 선분의 끝점의 방향들로 두 선분이 교차하는지 확인한다. 풀이 def solution(): def ccw(a, b, c): return (a[0]*b[1]+b[0]*c[1]+c[0]*a[1])-(b[0]*a[1]+c[0]*b[1]+a[0]*c[1]) x1, y1, x2, y2 = map(int, input().split()) x3, y3, x4, y4 = map(int, input().split()) p1, p2, p3, p4 = (x1, y1), (x2, y2), (x3, y3), (x4, y4) l1 = ccw(p1, p2, p3)*ccw(p1, p2, p4) l2 = ccw(p3, p4, p1)*ccw(p3, p4, p2)..

아이디어 DFS로 경로의 수를 계산하되, 동적 계획법으로 이미 방문한 칸의 이후 경로의 수는 저장하여 빠르게 계산한다. 풀이 import sys input = sys.stdin.readline def dfs(idx, r, c): if dp[r][c][idx] >= 0: return dp[r][c][idx] if board[r][c] != word[idx]: dp[r][c][idx] = 0 return 0 if idx == 0: dp[r][c][idx] = 1 return 1 dp[r][c][idx] = 0 for k in range(-K, K+1): if k: nr, nc = r+k, c+k if N > nr >= 0: dp[r][c][idx] += dfs(idx-1, nr, c) if M > nc >=..

아이디어 다익스트라를 이용해 목적지 후보에 도착하는 최단 시간과 g와 h 교차로를 거쳐 도착하는 최단 시간을 비교한다. 풀이 import sys from heapq import heappush, heappop input = sys.stdin.readline INF = int(1e9) def solution(): T = int(input()) for _ in range(T): n, m, t = map(int, input().split()) s, g, h = map(int, input().split()) graph = [[] for _ in range(n+1)] for _ in range(m): a, b, d = map(int, input().split()) graph[a].append((b, d)) gra..