[백준/27315] 틀리는 건 싫으니까 쉬운 문제에 올인하려 합니다 (Python)

Problem :

 

Difficulty :

 

Status :

 

Time :

 

---

 

문제 설명

 

한별이는 BOJ 랭킹을 올리기 위해 BOJ에서 M개의 문제를 풀려고 한다. 하지만 한별이는 틀렸습니다를 보는 것을 매우 싫어한다. 따라서 최소한으로 틀리면서 M개의 문제를 푸는 방법을 생각하기로 했다.

각 문제는 아이디어 난이도와 구현 난이도를 가진다. 아이디어 난이도가 한별이의 능력보다 높은 경우 한별이는 문제의 풀이조차 떠올릴 수 없기 때문에 문제를 풀 수 없다.

구현 난이도가 아무리 높더라도 아이디어 난이도가 한별이 아이디어 능력 이하라면 오랜 시간을 들여 문제를 푸는 것이 가능하다. 그러나 구현 난이도가 한별이의 구현 능력보다 높은 문제는 이 과정에서 구현 난이도-한별이의 구현 능력만큼 틀렸습니다를 받게 된다. 구현 난이도가 한별이의 구현 능력 이하인 문제는 틀렸습니다 없이 한번에 맞출 수 있다.

단, 데이터가 있는 문제의 경우 한별이는 데이터를 보면서 미리 답을 맞추어가기 때문에 틀렸습니다를 받지 않는다. 그리고 에디토리얼이 있는 경우, 한별이는 그 에디토리얼을 이해할 수 있으면 에디토리얼을 보며 구현을 한다. 한별이가 에디토리얼을 이해하기 위해서는 한별이의 아이디어 능력*2 >= 문제의 아이디어 난이도 이어야 한다. 에디토리얼을 보며 구현하는 경우 구현 난이도와 아이디어 난이도는 각각 floor(구현난이도/2), floor(아이디어난이도/2)로 줄어든다.

문제를 1개씩 풀 때마다 한별이의 아이디어 능력과 구현 능력은 1씩 올라간다.

이때 BOJ에 있는 N개의 문제 가운데 M개를 풀 때 받아야 하는 틀렸습니다의 최솟값을 구한다. M개의 문제를 풀 수 없는 경우 -1을 출력한다.

 

입력 및 출력

 

입력

 

첫 번째 줄에 두 정수 N, M이 공백으로 구분되어 주어진다. (1 <= M <= N <= 500,000)

다음 N개의 줄에 D_i  P_i T_i E_i의 네 정수로 각각 문제의 아이디어 난이도, 구현 난이도와 데이터 소유 여부, 에디토리얼 소유 여부가 공백으로 구분되어 주어진다.

 

•  1 <= D_i, P_i <= 10^9
• T_i가 0인 경우 데이터 없음, 1인 경우 데이터 있음
• E_i가 0인 경우 에디토리얼 없음, 1인 경우 에디토리얼 있음

마지막 줄에 한별이의 아이디어 능력과 구현 능력을 나타내는 정수 HD, HP가 주어진다. (1 <= HD,HP <= 10^9)

 

출력

 

BOJ에 있는 N개의 문제 가운데 M개를 풀 때 받아야 하는 틀렸습니다의 최솟값을 출력한다. M개의 문제를 풀 수 없는 경우 -1을 출력한다.

 

입력 예시

 

4 3
3 4 1 0
2 3 0 0
3 6 1 1
1 5 0 1
1 1

 

출력 예시

 

1

 

 

---

 

풀이

 

우선 그리디하게 생각해 볼 수 있다. HD >= D를 만족하는 모든 문제중, P가 가장 낮은 문제를 반복해서 푸는 것이다. 이 때 더해지는 틀렸습니다 값은 max(P - HP, 0)이 된다.

 

• T = 1인 경우, P = 0으로 취급하는 것과 동일하다.
• E = 1인 경우, HD >= D/2인 모든 문제에서 floor(D/2), floor(P/2)로 취급할 수 있다. 그런데 HD, D 모두 자연수이므로 사실상 ceil(D/2), floor(P/2)로 취급하는 것과 동일하다 (HD >= ceil(D/2) >= D/2 이므로)

 

 

풀이 코드

from heapq import heappush, heappop
import sys
import math
input = sys.stdin.readline

N, M = map(int, input().split())
problem_list = list()
solvable_problem_list = list()
for _ in range(N) :
  D, P, T, E = map(int, input().split())
  _D, _P = D, P
  if T == 1 :
    P, _P = 0, 0
  if E == 1 :
    heappush(problem_list, (math.ceil(D / 2), P // 2))
  else :
    heappush(problem_list, (D, P))
HD, HP = map(int, input().split())

answer = 0
while M :
  while problem_list and HD >= problem_list[0][0] :
    D, P = heappop(problem_list)
    heappush(solvable_problem_list, P)
  if not solvable_problem_list :
    break
  P = heappop(solvable_problem_list)
  answer += max(P - HP, 0)
  HP += 1
  HD += 1
  M -= 1

print(answer if not M else -1)

풀이 완료!