본문 바로가기

분류 전체보기

(402)
[백준 2001번] 보석 줍기 (Python3) import sys input = sys.stdin.readline def DFS(now,bit,cnt): if graph[now][0] >= cnt: DP[now][bit] = cnt for next in range(1,K+1): if bit&(1
[백준 1944번] 복제 로봇 (Python3) import sys,collections,heapq input = sys.stdin.readline dy = [1,-1,0,0] dx = [0,0,1,-1] def find(): for y in range(N): for x in range(N): if board[y][x]=="S" or board[y][x]=="K": Index[(y,x)] = len(location) location.append((y,x)) def BFS(y,x,now): cnt = 0 visited = [[0]*N for i in range(N)] dq = collections.deque([(y,x,0)]) while dq: y,x,d = dq.popleft() if visited[y][x]: continue visited[y][x]..
[백준 1933번] 스카이라인 (Python3) import sys input = sys.stdin.readline from heapq import * N = int(input()) stack = [] hq = [] for i in range(N): heappush(hq,tuple(map(int,input().split()))) end = 0 while hq: l,h,r = heappop(hq) if l >= end: if l > end: stack.append((end,0)) stack.append((l,h)) else: if h != stack[-1][1]: stack.append((l,h)) end = r continue if h end: heappush(hq,(end,h,r)) continue if end > r: heappush(hq,(r,s..
[백준 16161번] 가장 긴 증가하는 팰린드롬 부분수열 (Python3) N,data = int(input()),[*map(int,input().split())] result = 1 i = 0 while i data[i+1]: i += 1 continue if data[i] == data[i+1]: result = max(result,2) i += 1 continue stack,l = [data[i]],1 while i
[백준 13711번] LCS 4 (Python3) def updateseg(i,v,start,end,x): if start==end: seg[x] = v else: mid = (start+end)//2 if i
[백준 17831번] 대기업 승범이네 (Python3) import sys input = sys.stdin.readline sys.setrecursionlimit(10**7) def DFS(x): diff = [] if not child[x]: return for c in child[x]: DFS(c) DP[x][0] += max(DP[c]) diff.append(DP[c][0]-max(DP[c])+score[x]*score[c]) DP[x][1] = DP[x][0]+max(diff) N = int(input()) parent = [0]+[*map(int,input().split())] score = [0]+[*map(int,input().split())] child = [[] for i in range(N+1)] for i in range(N): child..
[백준 3860번] 할로윈 묘지 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] def BFS(e): visited = [[0]*M for i in range(N)] y,x,t = hole[e] dq = deque([(y,x,0)]) while dq: y,x,d = dq.popleft() if visited[y][x]: continue visited[y][x] = 1 if board[y][x]: graph.append((e,board[y][x],d+t)) continue for i in range(4): y1,x1 = y+dy[i],x+dx[i] if N>y1>=0 and M>x1>=0 and not vis..
[백준 12846번] 무서운 아르바이트 (Python3) N,data = int(input()),[*map(int,input().split())]+[0] histogram,result = [],0 for i in range(N+1): j = i while histogram and histogram[-1][0]>=data[i]: h,j = histogram.pop() result = max(result,h*(i-j)) histogram.append((data[i],j)) print(result) 히스토그램에서 가장 큰 직사각형 [백준 6549번] 히스토그램에서 가장 큰 직사각형 (Python3) (tistory.com) 문제와 완전히 똑같은 문제이다. 기존의 코드에서 data에 0을 추가하는 방식으로 약간의 코드개선을 하였다.