본문 바로가기

분류 전체보기

 (402)
[백준 23291번] 어항 정리 (Python3) import sys input = sys.stdin.readline dy = [1,0,-1,0] dx = [0,1,0,-1] def roll(): global fishbowl h = len(fishbowl) if h==1: w = 1 else: w = len(fishbowl[-1]) if len(fishbowl[0])-w < h: return False newfishbowl = [[0]*h for i in range(w+1)] newfishbowl[0] = fishbowl[0][w:] for y in range(h): for x in range(w): newfishbowl[w-x][y] = fishbowl[y][x] fishbowl = newfishbowl return True def distribute..
[백준 7869번] 두 원 (Python3) import sys input = sys.stdin.readline from math import sqrt,pi,sin,acos def coslaw(a,b,c): cosA = (b**2+c**2-a**2)/(2*b*c) return acos(cosA) x1,y1,r1,x2,y2,r2 = map(float,input().split()) c = sqrt((x1-x2)**2+(y1-y2)**2) if not r1 or not r2 or c>=r1+r2: result = 0 elif c
[백준 1949번] 우수 마을 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) def DFS(last,now): DP1[now] += population[now] diff = [] for next in graph[now]: if next == last: continue DFS(now,next) DP23next = max(DP2[next],DP3[next]) DP1[now] += DP23next DP2[now] += max(DP1[next],DP3[next]) DP3[now] += DP23next diff.append(DP1[next]-DP23next) if diff: diff.sort(reverse=True) if diff[0] < 0: DP3[now] += di..
[백준 11780번] 플로이드 2 (Python3) import sys input = sys.stdin.readline INF = 10**9 N,M = int(input()),int(input()) graph = [[INF]*(N+1) for i in range(N+1)] path = [[[i] for i in range(N+1)] for i in range(N+1)] for i in range(M): x,y,w = map(int,input().split()) graph[x][y] = min(graph[x][y],w) for k in range(1,N+1): for i in range(1,N+1): for j in range(1,N+1): if i == j: continue if graph[i][j] > graph[i][k]+graph[k][j]: gra..
[백준 1725번] 히스토그램 (Python3) import sys input = sys.stdin.readline from heapq import heappush,heappop N = int(input()) result = 0 hq = [] for i in range(N): h = int(input()) heappush(hq,(-h,i)) while hq and -hq[0][0]>h: h1,i1 = heappop(hq) result = max(result,-h1*(i-i1)) heappush(hq,(-h,i1)) while hq: h,i = heappop(hq) result = max(result,-h*(N-i)) print(result) 우선순위 큐를 이용해서 해결하였다. 보통 세그먼트 트리, 분할정복을 이용해서 푼다고 하는데, 그 방법으로 어떻게..
[백준 11066번] 파일 합치기 (Python3) import sys input = sys.stdin.readline INF = 10**9 T = int(input()) for test in range(T): N = int(input()) data = [*map(int,input().split())] sumlist = [0] for i in range(N): sumlist.append((sumlist[-1]+data[i])) DP = [[INF]*N for i in range(N)] for i in range(N): DP[i][i] = 0 for k in range(1,N): for i in range(N-k): for j in range(i,i+k): DP[i][i+k] = min(DP[i][i+k],DP[i][j]+DP[j+1][i+k]+sumlis..
[백준 11049번] 행렬 곱셈 순서 (Python3) import sys input = sys.stdin.readline INF = 10**12 N = int(input()) matrix = [] for i in range(N): matrix.append([*map(int,input().split())]) DP = [[INF]*N for i in range(N)] for i in range(N): DP[i][i] = 0 for k in range(1,N): for i in range(N-k): for j in range(i,i+k): DP[i][i+k] = min(DP[i][i+k],DP[i][j]+DP[j+1][i+k]+matrix[i][0]*matrix[j][1]*matrix[i+k][1]) print(DP[0][N-1]) 대략 한달이 넘도록 풀지 못했..
[백준 9370번] 미확인 도착지 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**5) from heapq import heappush,heappop INF = 10**9 def DFS(n,now): if n in result: return if now==start: return for last in path[now]: if last==g and now==h or now==g and last==h: result.add(n) return DFS(n,last) def Djikstra(): DP = [INF]*(N+1) hq = [] heappush(hq,(0,start,start)) while hq: w,now,last = heappop(hq) if DP[now] < w: c..

티스토리툴바