흙금이네 블로그

아이디어 문자열 내에서 단어의 시작과 끝 인덱스를 그래프로 표현하고 BFS로 문자열을 만들 수 있는지 확인한다. 풀이 import sys input = sys.stdin.readline def solution(): S = input().rstrip() M = len(S) N = int(input()) graph = [[] for _ in range(101)] for _ in range(N): a = input().rstrip() l = len(a) idx = S.find(a, 0) while idx >= 0: graph[idx].append(idx+l) idx = S.find(a, idx+l) visited = [0]*101 visited[0] = 1 stack = [0] while stack: u = ..

아이디어 상민이와 지수가 선물을 포장하는 시간을 정렬하여 순번에 따라 선물 번호를 할당한다. 풀이 import sys input = sys.stdin.readline def solution(): A, B, N = map(int, input().split()) S, J = [(-A+1, 0)], [(-B+1, 1)] total = 0 for i in range(1, N+1): t, c, m = input().split() t, m = int(t), int(m) total += m if c == 'B': last = max(S[-1][0]+A, t) for d in range(m): S.append((last+A*d, 0)) else: last = max(J[-1][0]+B, t) for d in range..

아이디어 친구들이 없는 틈시간을 내림차순으로 정렬하여 난로를 끌 수 있는 시간을 구한다. 풀이 import sys input = sys.stdin.readline N, K = map(int, input().split()) T = [int(input()) for _ in range(N)] D = sorted([T[i+1]-T[i]-1 for i in range(N-1)], reverse=True) print(T[-1]-T[0]-sum(D[:K-1])+1)

아이디어 전화를 넘겨 받을 수 있는 부원을 선행으로 위상 정렬하여 진입 차수가 0이 되는 부원의 수를 구한다. 풀이 진입 차수가 0이 되지 않는 부원들은 사이클이 발생하는 구간에 존재한다. import sys input = sys.stdin.readline def solution(): N, M = map(int, input().split()) graph = [dict() for _ in range(N+1)] D = [0]*(N+1) for _ in range(M): U, V = map(int, input().split()) if graph[V].get(U, 0) == 0: graph[V][U] = 1 D[U] += 1 stack = [] for i in range(1, N+1): if D[i] == 0:..

아이디어 다익스트라로 2번 정점까지의 최단 거리를 구한 후, 트리에서의 동적 계획법으로 경로의 수를 구한다. 풀이 import sys from heapq import heappush, heappop sys.setrecursionlimit(int(1e5)) input = sys.stdin.readline INF = int(1e7) def solution(): def dfs(u): if dp[u]: return dp[u] if u == 2: return 1 for v, c in graph[u]: if D[v] < D[u]: dp[u] += dfs(v) return dp[u] N, M = map(int, input().split()) graph = [[] for _ in range(N+1)] for _ in ..

아이디어 크루스칼 알고리즘으로 최소 스패닝 트리를 구현하되, 고려하지 않아도 될 터널들은 제외하여 시간을 단축한다. 풀이 좌표 x, y, z 각각을 기준으로 행성들을 정렬하여 인접한 두 행성과 두 행성을 연결하는 데 필요한 비용만을 고려한다. 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()) planets = [] for i i..

아이디어 크루스칼 알고리즘으로 최소 스패닝 트리를 구현하여 최소 비용을 구한다. 풀이 가상의 0번째 논을 설정해 우물을 팔 때 드는 비용을 0번 논과 연결하는 데 드는 비용으로 저장하여 푼다. import sys input = sys.stdin.readline INF = int(1e8) 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)] e..

아이디어 최소 스패닝 트리로 모든 도시에 전기를 공급할 수 있는 최소 비용을 구한다. 풀이 #1 프림 알고리즘으로 최소 스패닝 트리를 구현한다. import sys from heapq import heappush, heappop input = sys.stdin.readline INF = int(1e7) def solution(): N, M, K = map(int, input().split()) plant = tuple(map(int, input().split())) graph = [dict() for _ in range(N+1)] for _ in range(M): u, v, w = map(int, input().split()) graph[u][v] = graph[v][u] = min(graph[u].ge..

아이디어 벨만-포드로 음의 사이클이 존재하는지 확인한다. 풀이 도로는 방향이 없고 웜홀은 방향이 있음에 주의해야 한다. 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 ..