백준 4716 풍선

작성일 | In |

문제 링크

  • https://www.acmicpc.net/problem/4716

알고리즘

  • 그리디
  • 정렬

풀이

문제 설명에서 주목해야 할 부분이 있는데, 하나는 풍선의 개수는 충분하다는 사실이며, 다른 하나는 입력 받는 순서대로 각 팀들에게 풍선이 주어지는 것이 아니라는 것이다.

따라서 어떤 방식으로 정렬할지 생각하는 게 중요하다.

A와 B 방으로부터 떨어진 거리 중에 큰 값 혹은 작은 값을 기준으로 정렬하는 방법은 아니었다.

그래서 풍선이 보관된 두 개의 방까지의 거리의 차이를 기준으로 정렬하는 방법을 써봤는데 성공했다.

  • A, B 방으로부터 떨어진 거리의 차이를 기준으로 내림차순 정렬을 실시한다.
  • 두 거리 중에 더 가까운(작은 값) 방에서부터 풍선을 가져온다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys
input = sys.stdin.readline

while True:
    n, a, b = map(int, input().split())
    
    if n == 0 and a == 0 and b == 0:
        break
        
    lst = []
    for i in range(n):
        lst.append(list(map(int, input().split())))
        
    lst.sort(key = lambda x : -abs(x[1] - x[2]))
    
    hab = 0
    for k, i, j in lst:
        if i <= j:
            dst = min(k, a)
            
        else:
            dst = k - min(k, b)
            
        hab += i * dst + j * (k - dst)
        
        a -= dst
        b -= k - dst
        
        
    print(hab)