백준 4716 풍선

문제

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

풀이

이 문제에서 가장 중요했던 점은 풍선이 부족한 경우가 없다는 것이다. 그렇기 때문에 각 팀마다 A또는 B에서 풍선을 무조건 하나씩 가져갈 수 있다. 각 팀마다 부족한 경우 없이 모두 가져갈 수 있기 떄문에, 거리차이를 기준으로 역으로 정렬해야 한다. 팀을 순회 하면서 만약 더이상 풍선을 가져올 수 없는 방이라면 다른 방에서 가져와야 한다.

while True:
    n,a,b = list(map(int,input().split()))
    if n == 0 and a == 0 and b == 0:
        break
    arr = []
    for i in range(n):
        arr.append(list(map(int,input().split())))
    arr.sort(key = lambda x : abs(x[1]-x[2]),reverse= True)
    ans = 0
    temp = []
    for i in range(n):
        k,da,db = arr[i]
        x = 0
        if da <= db:
            x = min(k,a)
            ans += da*x
            ans += db*(k-x)
            a -= x; b -= (k-x)
        elif da > db:
            x = min(k,b)
            ans += da*(k-x)
            ans += db*x
            a -= (k-x); b -= x
        else:
            temp.append([k,da,db])
    print(ans)

boj 카테고리 내 다른 글 보러가기