[TIL_Carrotww] 113 - 23/05/16

📝Carrotww의 코딩 기록장

🧲 python algorithm

🔍 백준 파일 합치기 3

골드 문제지만 우선순위 큐를 쓴다는 사실만 알아내면 쉽게 풀 수 있다.

def solve():
    import sys
    import heapq

    T = int(sys.stdin.readline())
    for _ in range(T):
        N = int(sys.stdin.readline())
        heap = list(map(int, sys.stdin.readline().split()))
        heapq.heapify(heap)
        result_cnt = 0

        while len(heap) > 1:
            t1 = heapq.heappop(heap)
            t2 = heapq.heappop(heap)

            t_sum = t1 + t2
            result_cnt += t_sum

            heapq.heappush(heap, t_sum)
        print(result_cnt)

if __name__ == "__main__":
    solve()

🔍 백준 컵라면

사실 이 문제를 풀고 위 문제를 풀었는데 그래서 쉽게 우선순위 큐라고 접근할 수 있었던 것 같다
이 문제도 우선순위 큐로 풀면 쉽게 풀린다.

def solve():
    import sys, heapq

    N = int(sys.stdin.readline())
    problem_list = []

    for _ in range(N):
        dead, cup = map(int, sys.stdin.readline().split())
        problem_list.append([dead, cup])

    problem_list.sort()

    heap = []

    for dead, cup in problem_list:
        heapq.heappush(heap, cup)

        if len(heap) > dead:
            heapq.heappop(heap)

    print(sum(heap))

if __name__ == "__main__":
    solve()