흙금이네 블로그

아이디어 벨만-포드로 음의 사이클이 존재하는지 확인한다. 풀이 도로는 방향이 없고 웜홀은 방향이 있음에 주의해야 한다. import sys input = sys.stdin.readline INF = int(1e11) def solution(): TC = int(input()) for _ in range(TC): N, M, W = map(int, input().split()) graph = [dict() for _ in range(N+1)] for _ in range(M): S, E, T = map(int, input().split()) graph[S][E] = min(graph[S].get(E, INF), T) graph[E][S] = min(graph[E].get(S, INF), T) for _ in ..

아이디어 N의 자릿값에 따라 각 숫자가 나오는 횟수를 계산한다. 풀이 def solution(): N = int(input()) number = list(map(int, [*str(N)]))[::-1] M = len(number) res = [0]*10 for i in range(M-1): p = 10**i if i == 0: res[0] += N//10 else: if number[i] > 0: res[0] += (N//(p*10))*p else: res[0] += (N//(p*10)-1)*p+(N%p+1) for i in range(M): p = 10**i for num in range(1, 10): if number[i] > num: if i == 0: res[num] += N//10+1 elif ..

아이디어 동적 계획법으로 서로 인접하지 않은 색을 고를 수 있는 경우의 수를 구한다. 풀이 def solution(): N = int(input()) K = int(input()) p = 1000000003 if K > N//2: print(0) return dp = [[0]*N for _ in range(N//2+1)] dp[1] = [1]*N for i in range(2, N//2+1): for j in range(N-3): dp[i][j+2] = (dp[i][j+1]+dp[i-1][j])%p dp[i][-1] = dp[i][-2] res = 0 for j in range(N): res = (res+dp[K][j])%p print(res) solution()

아이디어 #1 BFS로 세 그룹의 돌이 개수가 같아질 수 있는지 확인한다. 풀이 #1 import sys input = sys.stdin.readline def solution(): A, B, C = map(int, input().split()) if (A+B+C)%3: print(0) else: visited = dict() queue = [tuple(sorted([A, B, C]))] visited[queue[0]] = 1 while queue: a, b, c = queue.pop(0) if a == b == c: print(1) break if a != b: temp = tuple(sorted([a+a, b-a, c])) if visited.get(temp, 0) == 0: visited[temp]..

아이디어 유니온 파인드로 한 개 이상의 변이 만나는 직사각형들의 집합 개수를 구한다. 풀이 (0, 0)을 지나는 직사각형을 고려해 (0, 0)에 크기가 0인 직사각형을 하나 추가하고, 직사각형 집합 개수-1을 출력한다. import sys input = sys.stdin.readline def solution(): def find(n): temp = n while n != group[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 N = int(input()) group = [i for i in range(N+1)] r..

아이디어 체스판을 갱신하며 9초 이상 캐릭터가 이동할 수 있는지 확인한다. 풀이 delta = [(0, 0), (-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)] def solution(): board = [[*input()] for _ in range(8)] visited = [[0]*8 for _ in range(8)] visited[7][0] = 1 stack = [(7, 0)] t = 1 while stack and t nr >= 0 and 8 > nc ..

아이디어 BFS로 방문하는 칸에 거울을 설치할 수 있는지에 따라 방향을 회전하며 설치해야 할 거울의 최소 개수를 구한다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): N = int(input()) board = [[*input().rstrip()] for _ in range(N)] doors = [] for r in range(N): for c in range(N): if board[r][c] == '#': doors.append((r, c)) stack = [] for d in range(4): stack.append((*doors[0], d)) cnt = 1 while..

아이디어 벨만-포드로 1번 도시에서 나머지 도시로 가는 가장 빠른 시간과 음의 사이클 여부를 확인한다. 풀이 두 도시 간 버스 노선이 여러 개일 수 있으므로 두 도시 간 이동 시간이 최소인 노선 정보를 저장한다. import sys input = sys.stdin.readline INF = int(1e11) def solution(): N, M = map(int, input().split()) graph = [dict() for _ in range(N+1)] for _ in range(M): A, B, C = map(int, input().split()) graph[A][B] = min(graph[A].get(B, INF), C) D = [INF]*(N+1) D[1] = 0 for _ in range(N..

아이디어 이분 탐색으로 가능한 최소 차이를 찾아 나가며, 방문할 칸의 값 범위를 제한하여 여러 경로를 방문할 수 있도록 한다. 풀이 import sys input = sys.stdin.readline delta = [(-1, 0), (0, 1), (1, 0), (0, -1)] def solution(): n = int(input()) board = [] numbers = set() for _ in range(n): board.append(tuple(map(int, input().split()))) numbers.update({*board[-1]}) numbers = sorted(numbers) s, e = 0, numbers[-1]-numbers[0] while s = board[0][0] >= i: v..

아이디어 #1 세트를 이용해 연산을 K번 수행했을 때 나올 수 있는 수의 최댓값을 구한다. 풀이 #1 def solution(): N, K = input().split() K = int(K) M = len(N) numbers = [set() for _ in range(K+1)] numbers[0].add(N) for k in range(K): for number in numbers[k]: num = [*number] for i in range(M-1): for j in range(i+1, M): if i == 0 and num[j] == '0': continue num[i], num[j] = num[j], num[i] numbers[k+1].add(''.join(num)) num[i], num[j] = ..