본문 바로가기

분류 전체보기

(402)
[백준 11266번] 단절점 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def DFS(now,last): global id visited[now] = ID[now] = id cnt = 0; check = 0 for next in graph[now]: if next==last: continue if visited[next]: visited[now] = min(visited[now],ID[next]) else: cnt += 1; id += 1 DFS(next,now) if visited[next] >= ID[now]: check = 1 visited[now] = min(visited[now],visited[next]) if ID[now]!=1 and check..
[백준 13907번] 세금 (Python3) import sys input = sys.stdin.readline from heapq import * N,M,K = map(int,input().split()) start,end = map(int,input().split()) graph = [[] for i in range(N+1)] for _ in range(M): a,b,w = map(int,input().split()) graph[a].append((b,w)) graph[b].append((a,w)) DP,CNT = [1e9]*(N+1),[0]*(N+1) hq = [(0,0,start)] while hq: w,cnt,now = heappop(hq) if DP[now] CNT[now] or DP[cnt][now]
[백준 13141번] Ignition (Python3) import sys input = sys.stdin.readline N,M = map(int,input().split()) DP = [[1e9]*N for i in range(N)] graph = [] for _ in range(M): a,b,c = map(int,input().split()) DP[a-1][b-1] = DP[b-1][a-1] = min(DP[a-1][b-1],c) graph.append((a-1,b-1,c)) for k in range(N): for i in range(N): for j in range(N): DP[i][j] = min(DP[i][j],DP[i][k]+DP[k][j]) for i in range(N): DP[i][i] = 0 result = 1e9 for i in ran..
[백준 2150번] Strongly Connected Component (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def DFS(now): global num nownum = num visited[now] = num stack.append(now) for next in graph[now]: if not visited[next]: num += 1 DFS(next) visited[now] = min(visited[now],visited[next]) if visited[now] == nownum: scc.append([]) while 1: x = stack.pop() visited[x] = 1e6 scc[-1].append(x) if x==now: break N,M = map(int,input().spl..
[백준 6091번] 핑크 플로이드 (Python3) import sys input = sys.stdin.readline from heapq import * def findparent(x): if parent[x] != x: parent[x] = findparent(parent[x]) return parent[x] N = int(input()) hq = [] for i in range(1,N): data = [*map(int,input().split())] for j in range(i+1,N+1): heappush(hq,(data[j-1-i],i,j)) parent = [i for i in range(N+1)] tree = [[] for i in range(N+1)] for i in range(N-1): while 1: w,x,y = heappop(hq)..
[백준 2254번] 감옥 건설 (Python3) import sys,math input = sys.stdin.readline from heapq import * def CCW(y1,x1,y2,x2,y3,x3): return (x1-x2)*(y3-y2)-(x3-x2)*(y1-y2) def convexhull(): global co if not co: return inside = False y,x = co[0] if y==Py and x==Px: inside = True convex = [(y,x)]; newco = [] hq = [] for i in range(1,len(co)): yi,xi = co[i] d = math.sqrt((x-xi)**2+(y-yi)**2) heappush(hq,((x-xi)/d,d,yi,xi)) while hq: cos,d,..
[백준 11570번] 환상의 듀엣 (Python3) import sys sys.setrecursionlimit(10**5) N = int(input()) note = [*map(int,input().split())] def DFS(n1,n2): if n2==N-1: return if not DP[n1][n2+1]: DFS(n1,n2+1) if not DP[n2][n2+1]: DFS(n2,n2+1) DP[n1][n2] = min(DP[n1][n2+1]+graph[n2][n2+1],DP[n2][n2+1]+graph[n1][n2+1]) graph = [[0]*N for i in range(N)] for i in range(N-1): for j in range(i+1,N): graph[i][j] = abs(note[i]-note[j]) DP = [[0]*N fo..
[백준 12872번] 플레이리스트 (Python3) N,M,P = map(int,input().split()) mod = 10**9+7 def cal(N): result = 1 for i in range(P): result *= N-min(i,M); result %= mod return result combination = [1] for i in range(P): combination.append(combination[-1]*(N-i)//(i+1)) result = 0 for n in range(P): result += combination[n]*cal(N-n)*(-1)**(n%2); result %= mod print(result) 조합을 이용해서 해결하였다. 사실 처음에는 "모든 노래를 플레이리스트에 추가해야 한다" 라는 말을 못봤었다. 그래서 코드의..