본문 바로가기

분류 전체보기

 (402)
[백준 14865번] 곡선 자르기 (Python3) import sys input = sys.stdin.readline N = int(input()) Q = [] for _ in range(N): x,y = map(int,input().split()) if not Q: if y!=0: Q.append((x,y)) continue if y==0 and Q[-1][1]>0: Q.append((x,-1)) elif y*Q[-1][1]0: Q.pop(0) if Q[0][1]last: small += 1 if s>end: big += 1 end = e last = e print(big,small) 문제를 잘못읽어서 약간 더 어렵게 해결한 문제. 아이디어 자체는 매우 간단한 문제인데 구현이 까다로울 수 있다. 풀이를 설명하면, 1. 입력되는 좌표가 음수에서 양수, ..
[백준 1506번] 경찰서 (Python3) import sys input = sys.stdin.readline def DFS(now): global id,result visited[now] = nowid = id stack.append(now) for next in range(N): if graph[now][next]: if not visited[next]: id += 1 DFS(next) visited[now] = min(visited[now],visited[next]) if visited[now] == nowid: c = 1e9 while 1: x = stack.pop() c = min(c,cost[x]); visited[x] = 1e9 if x==now: result += c return N = int(input()) cost = [*map..
[백준 4196번] 도미노 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**7) def DFS(now): global id stack.append(now) visited[now] = nowid = id for next in graph[now]: if not visited[next]: id += 1 DFS(next) if visited[next]
[백준 2021번] 최소 환승 경로 (Python3) import sys,collections input = sys.stdin.readline def BFS(): dq = collections.deque([(i,0) for i in graph[start]]) visitedN = [0]*(N+1); visitedL = [0]*L while dq: now,cnt = dq.popleft() if visitedL[now]: continue visitedL[now] = 1 for s in subway[now]: if s==end: return cnt if visitedN[s]: continue visitedN[s] = 1 for next in graph[s]: if not visitedL[next]: dq.append((next,cnt+1)) return -1 N,..
[백준 1854번] K번째 최단경로 찾기 (Python3) import sys input = sys.stdin.readline from heapq import * N,M,K = map(int,input().split()) graph = [[] for i in range(N+1)] for _ in range(M): x,y,w = map(int,input().split()) graph[x].append((y,w)) hq = [(0,1)]; distance = [[] for i in range(N+1)] while hq: w,now = heappop(hq) if len(distance[now])==K: if w >= -distance[now][0]: continue else: heappop(distance[now]) heappush(distance[now],-w) f..
[백준 1738번] 골목길 (Python3) import sys input = sys.stdin.readline N,M = map(int,input().split()) graph = [[*map(int,input().split())] for i in range(M)] DP = [-1e9]*(N+1); DP[1] = 0 path = [1]*(N+1); cycle = set() for i in range(N): for u,v,w in graph: if DP[u]==-1e9: continue if DP[v] < DP[u]+w: DP[v] = DP[u]+w; path[v] = u if i==N-1: cycle.add(v) DP2 = [-1e9]*(N+1); DP2[N] = 0 for i in range(N-1): for v,u,w in graph: if ..
[백준 3830번] 교수님은 기다리지 않는다 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**6) def union(x,y,w): value[x] -= w parent[x] = y parentvalue[x] = value[y] def findparent(x): if parent[x] != x: p,pv = parent[x],parentvalue[x] parent[x] = findparent(p) value[x] += value[p]-pv parentvalue[x] = value[parent[x]] return parent[x] while 1: N,M = map(int,input().split()) if not N: break parent = [i for i in range(N+1)]..
[백준 1849번] 순열 (Python3) import sys input = sys.stdin.readline def updatefenwick(i): if not i: return while ix1: return find(x,i+2**c,c-1) if x

티스토리툴바