[Python 3] BOJ - 2786 "상근이의 레스토랑"

 # 문제 링크

https://www.acmicpc.net/problem/2786

2786번: 상근이의 레스토랑

 

 # 풀이

 개인적으로 이 문제의 핵심은 그리디 알고리즘이라고 생각한다. 설명의 편의를 위하 물건 i가 있을때, 첫번째로 구매할 때 지불해야 하는 가격을 $a_i$, 첫번째로 구매하지 않을 때 지불해야 하는 가격을 $b_i$라고 하자.

<그림 1. N = 8이고 현재 5개만 뽑은 경우>

 위 그림 1의 경우를 생각해보자. 그림 1에서 첫번째로 구매하는 물건은 물음표, 첫번째가 아닌 두번째부터 다섯번째 구매하는 물건은 느낌표로 나타내었다. 이 때, 느낌표에만 집중해보자. 어떻게 하면 느낌표의 합을 최소화할 수 있을까?

 간단하다. 8개의 물건 중에서 $b_i$ 기준으로 가장 작은 4개를 고르면 된다. 그렇다면 전체적으로 최소가 되게 하려면 남은 것은 물음표를 최소화하면 된다. 이것 역시 간단하다. 앞에서 뽑은 4개의 느낌표에는 속하지 않는 남은 4개의 물건 들 중에서 $a_i$가 가장 작은 것을 선택하면 된다.

<그림 2. N = 8이고 현재 5개만 뽑은 경우>

 그런데 그림 1로만 뽑으면 항상 최적일까? 위 그림 2의 경우를 생각해보자. 그림 2는 5개를 뽑을 때 모두 $b_i$로 뽑는다고 가정한다. 그런데 문제에서는 반드시 하나를 $b_i$가 아닌 $a_i$로 뽑아야 하므로 다섯개 중 하나는 무조건 물음표가 되어야 한다. 그런데, 그 때 물음표를 바꾸게 된다면 바뀌게 되는 가격의 변동은 $a_i - b_i$이다. 그런데 우리는 가격의 총합을 최소화해야 하므로 가격의 변동이 가장 작은 느낌표를 물음표로 바꾸면 된다.

 위 그림 1과 그림 2의 논리는 비슷하게 보이지만 다르다. 그림 1은 단순히 그 순간에서 남은 물건의 $a_i$ 중 최소값만 가져오는 전략, 즉 $a_i$의 절댓값 자체에 집중을 하는 전략이다. 그러나 그림 2는 단순히 $a_i$가 작은 것보다는 이미 뽑았던 값들 중에서 가장 효율적인 값에 집중하는 전략이기에 어느 하나의 전략만으로만 시도하면 다른 경우에서 발생할 수 있는 최소값을 발견하지 못해 오답을 낼 수 있다.

 

 # 코드

import sys, heapq

# 입력부
n = int(sys.stdin.readline())
arr = []
for i in range(n):
    a, b = map(int, sys.stdin.readline().split())
    arr.append((a,b))

# b_i 기준을 정렬
arr.sort(key=lambda x : (x[1]))

# cache : n-1부터 i까지 a_i 중 가장 작은 값을 저장하는 배열(suffix minimum) 
cache = [0] * n

# ans : 정답 배열
ans = [98765432109876543210] * n

# 초기화 및 suffix 순서에 따라 값을 채움
cache[-1] = arr[-1][0]
for i in range(n - 2, -1, -1):
    cache[i] = min(cache[i + 1], arr[i][0])
    
# 전략 1. 현재 인덱스가 i라면, i - 1까지는 그대로 더하고 cache[i]값을 더함
now = 0
for i in range(n):
    ans[i] = min(ans[i], now + cache[i])
    now += arr[i][1]
    
# q : a_i - b_i 기준으로 하는 최소 힙
q = []
now = 0

# 전략 2. 현재 뽑았던 것들 중에서 이득이 가장 큰 물건을 첫번째로 뽑음
for i in range(n):
    now += arr[i][1]
    heapq.heappush(q, arr[i][0] - arr[i][1])
    ans[i] = min(ans[i], now + q[0])
    
# 정답 출력
for i in ans:
    print(i)