본문 바로가기

분류 전체보기

 (402)
[백준 1781번] 컵라면 (Python3) import sys input = sys.stdin.readline from heapq import heappop,heappush N = int(input()) ramen = [[] for i in range(N)] for i in range(N): d,r = map(int,input().split()) ramen[N-d].append(r) result = 0 hq = [] for i in range(N): for r in ramen[i]: heappush(hq,-r) if hq: result -= heappop(hq) print(result) 너무 간단한 우선순위 큐 활용 문제 데드라인이 가장 긴 문제부터 우선순위큐에 넣고 가장 컵라면을 많이 얻는 문제부터 풀면 된다. 뒤에서부터 세어야 한다는게 트릭이..
[백준 1234번] 크리스마스 트리 (Python3) import sys input = sys.stdin.readline from math import factorial c = [(0,1),(1,2),(0,2)] def combination(x,y): return factorial(x)//factorial(y)//factorial(x-y) def DFS(n,cnt): global result if n == N+1: result += cnt return for i in range(3): if RGB[i] >= n: RGB[i] -= n DFS(n+1,cnt) RGB[i] += n if not n%2: for i,j in c: if RGB[i] >= n//2 and RGB[j] >= n//2: RGB[i] -= n//2 RGB[j] -= n//2 DFS(n+1..
[백준 1572번, 9426번] 중앙값 측정 (Python3) import sys input = sys.stdin.readline from heapq import heappush,heappop INF = 10**6 N,K = map(int,input().split()) maxhq = [] minhq = [] heappush(maxhq,(INF,INF)) heappush(minhq,(INF,INF)) value = [0]*N result = 0 for i in range(N): n = int(input()) value[i] = n if n>minhq[0][0]: heappush(minhq,(n,i)) else: heappush(maxhq,(-n,i)) if i>=K: if maxhq[0][1] == i-K: heappop(maxhq) elif minhq[0][1] =..
[백준 1525번] 퍼즐 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [1,-1,0,0] dx = [0,0,1,-1] puzzle = "" for i in range(3): puzzle += "".join(input().split()) memory = set() result = -1 dq = deque() dq.append((puzzle,0)) while dq: p,cnt = dq.popleft() if p in memory: continue if p == "123456780": result = cnt break memory.add(p) zero = p.find("0") y,x = zero//3,zero%3 plist = [[*p[:3]],[*..
[백준 5373번] 큐빙 (Python3) import sys input = sys.stdin.readline from copy import deepcopy def turnplane(x): plane = [[0]*3 for i in range(3)] for i in range(3): for j in range(3): plane[j][2-i] = cube[x][i][j] cube[x] = plane #옆면 4개는 앞에서 바라볼때 기준 윗면 아랫면은 대칭 def turnside(x): if x == "U": a,b,c = cube["F"][0] cube["F"][0] = [*cube["R"][0]] cube["R"][0] = [*cube["B"][0]] cube["B"][0] = [*cube["L"][0]] cube["L"][0] = [a,b,c] ..
[백준 1377번] 버블 소트 (Python3) import sys input = sys.stdin.readline N = int(input()) A = [] for i in range(N): a = int(input()) A.append((a,i)) A.sort() maxdiff = 0 for i in range(N): a,i1 = A[i] maxdiff = max(maxdiff,i1-i) print(maxdiff+1) 아이디어를 떠올리기 살짝 어려웠던 문제였다. 중요한 포인트는 어떤 숫자가 정렬과정에서 앞으로 가는건 연산 한번에 몇번이고 할 수 있지만 뒤로 가는건 연산 한번에 단 한번밖에 하지 못한다는 것이다. 따라서 현재의 위치에서 정렬된 위치로 가는데 몇 번 뒤로 가야하는지의 최댓값을 계산하면 정답이 나온다. 이때 주의해야 할 점은 처음에 입력..
[백준 21611번] 마법사 상어와 블리자드 (Python3) import sys input = sys.stdin.readline from collections import deque dy = [0,1,0,-1] dx = [-1,0,1,0] def boom(seq): global result,boomed newseq = [] x = 0 while x
[백준 2613번] 숫자구슬 (Python3) import sys input = sys.stdin.readline from bisect import bisect_right def group(last,maxsum,cnt,groupcnt): global result1,result2 if maxsum >= result1: return if cnt == M-1: maxsum = max(maxsum,sumlist[-1]-sumlist[last]) if maxsum >= result1: return result1 = maxsum result2 = groupcnt + " " + str(N-last) return if M-cnt == N-last: maxsum = max(max(data[last:]),maxsum) if maxsum >= result1: retur..

티스토리툴바