[백준 4716번] 풍선 (Python3)

import sys
input = sys.stdin.readline

while True:
  N,A,B = map(int,input().split())
  if not N:
    break
  
  balloon = [0]*N
  diff = []
  
  SUM = 0
  for i in range(N):
    k,a,b = map(int,input().split())
    SUM += k*a
    balloon[i] = k
    diff.append((b-a,i))
    A -= k
  
  diff.sort()
  i = 0
  while i<N:
    d,n = diff[i]
    k = balloon[n]
    if A+k > 0:
      break
    A += k
    B -= k
    SUM += d*k
    i += 1
  balloon[n] += A
  SUM -= d*A
  B += A
  while i<N:
    d,n = diff[i]
    k = balloon[n]
    if d>=0 or B-k<0:
      break
    B -= k
    SUM += d*k
    i += 1
  if d<0:
    SUM += d*B
  
  print(SUM)

발상은 매우 쉬운데 구현이 살짝 까다로웠던 문제.

 

알고리즘을 요약하면,

1. 모든 팀의 풍선을 A에서 받았다고 가정하고 SUM을 구한 뒤, A에서 모든 풍선의 개수만큼 빼준다.

2. 모든 팀의 a와 b의 거리차(b-a)를 리스트로 만들고 정렬한다.

3. 거리차가 작은 순으로 A가 0이 될때까지 B에서 풍선을 받는다. SUM에서 거리차를 더해준다.

4. 남은 거리차가 음수면 B의 풍선이 다 닳지 않고, 거리차가 0보다 커지기 전까지 B에서 풍선을 받는다. SUM에서 거리차를 더해준다.

 

즉 쉽게 말해서 모든 풍선을 A에서 받은 뒤, 거리차를 기준으로 B에서 풍선을 차례대로 받는다고 생각하면 된다.

 

 

오늘의 교훈) 테스트케이스 개수를 주의하자