흙금이네 블로그

아이디어 막대기를 맞아 미네랄이 파괴된 칸을 기준으로 주변을 BFS하여 바닥에 닿아 있지 않은 클러스터들을 이동시킨다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): def throw(i, j): visited = [[0]*C for _ in range(R)] for di, dj in delta: ni, nj = i+di, j+dj if R > ni >= 0 and C > nj >= 0: if board[ni][nj] == 'x' and visited[ni][nj] == 0: visited[ni][nj] = 1 bottom = [-1]*C queue = [(ni, nj)] ..

아이디어 모듈러 연산의 분배법칙과 페르마의 소정리로 계산식을 바꾼 후, 이분 탐색을 이용해 계산한다. 풀이 \(\binom{N}{K}\)는 \(\frac{N!}{K!(N-K)!}\)이고, \(\frac{N!}{K!(N-K)!}=\frac{N\cdot(N-1)\cdot\cdots\cdot(N-K+1)}{K!}\)이다. 결과값은 1,000,000,007로 나눈 나머지이므로 계산 과정에서 모듈러 연산의 곱셈에 대한 분배법칙을 이용할 수 있다. \((a\bmod p)\cdot(b\bmod p)=ab\bmod p\) 따라서 계산 과정에서 발생하는 중간값들을 모두 1,000,000,007로 나눈 나머지로 두고 계산할 수 있다. 모듈러 연산의 곱셈에 대한 분배법칙으로 분모와 분자를 각각 1,000,000,007로 나..

아이디어 유니온 파인드와 BFS로 두 백조가 만나는 데 걸리는 일수를 찾는다. 풀이 import sys from collections import deque input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): def find(n): temp = n while group[n] != n: n = group[n] group[temp] = n return n def union(n1, n2): n1 = find(n1) n2 = find(n2) if n1 > n2: n1, n2 = n2, n1 group[n2] = n1 R, C = map(int, input().split()) board = [[*input().r..

아이디어 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..

아이디어 BFS로 탐색하며 방문한 더러운 칸의 개수에 따라 비트마스킹으로 방문 표시한다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): while 1: w, h = map(int, input().split()) if w == 0: break board = [[*input().rstrip()] for _ in range(h)] queue = [] total = 0 for r in range(h): for c in range(w): if board[r][c] == '*': board[r][c] = f'{1

아이디어 둘째 줄의 숫자를 인덱스로 하여 탐색해나갈 때 탐색을 시작한 인덱스로 되돌아오면 방문한 숫자들은 조건을 만족한다. 풀이 import sys input = sys.stdin.readline def solution(): N = int(input()) numbers = [0]+[int(input()) for _ in range(N)] visited = [0]*(N+1) for i in range(1, N+1): if visited[i] == 0: _visited = [0]*(N+1) _visited[numbers[i]] = 1 queue = [numbers[i]] j = 0 cnt = 1 while j < cnt: idx = queue[j] j += 1 if _visited[numbers[idx]] ..

아이디어 #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..