본문 바로가기

알고리즘/그리디

 (2)
파이썬 | 백준 | 1202 | 보석 도둑 solution 1. 힙 이용. 1) 가치 - 최대힙을 이용하여 pop하고 무게가 배낭의 수용 가능한 무게보다 작으면 결과에 더한다. 2) 배낭의 무게 - 최소힙을 이용하여 수용 가능한 무게가 작은 것부터 담을 수 있는 최대 무게를 구한다. →시간초과 # 1202, 보석 도둑 import sys import heapq N, K = map(int, sys.stdin.readline().split()) jewels = [] bags = [] for _ in range(N): M, V = map(int, sys.stdin.readline().split()) # 무게, 가격 heapq.heappush(jewels, ((-V, V), M)) for _ in range(K): heapq.heappush(bags, ..
파이썬 | 백준 | 9576 | 책 나눠주기 solution 1. 최소힙을 이용 (b 기준) 2. defaultdict 이용해 이미 나눠준 책인지 확인 # 9576, 책 나눠주기 import sys from collections import defaultdict import heapq T = int(sys.stdin.readline()) while T: shared = defaultdict(int) want = [] # N개의 서적을 M명에게 나눠줌 N, M = map(int, sys.stdin.readline().split()) cnt = 0 # 책 받은 사람 수 for _ in range(M): a, b = map(int, sys.stdin.readline().split()) heapq.heappush(want, (b, a)) while wan..

티스토리툴바