이번 문제는 그리디 알고리즘을 통해 해결하였다. 우선 정렬하는 방법이 가장 중요했는데, 이 부분에서 시행 착오를 겪었다. 처음에는 Da의 오름차순, Db의 내림차순을 적용하여 정렬하였다. 그러나 이 방법은 Db가 내림차순으로 정렬되지 않기 때문에 잘못된 방식이었다.

이에 대해 고민하던 중, Da-Db의 내림차순으로 정렬하고, 이를 순회하며 Da와 Db 중 더 작은 것을 먼저 취하는 방식으로 진행한다면 풀이가 될 것 같다는 생각을 하였다. 그래서 Da-Db의 내림차순으로 정렬하였고, 이를 순회하며 Da가 Db 이하일 경우, a에서 제공할 풍선의 갯수를 a와 K 중의 최솟값으로 구하고, 남은 풍선의 갯수를 b에서 제공해야 하기 때문에 이 수를 K-a와 K 중의 최솟값으로 구하였다. 그리고 주어진 거리만큼씩을 곱하여 결과 변수에 더하는 과정을 진행하였다. Da가 Db보다 크다면 이 과정을 반대로 진행하였다.

Code

while True:
    n, a, b = map(int, input().split())
    if (n, a, b) == (0, 0, 0):
        break
    info = sorted([list(map(int, input().split())) for _ in range(n)], key= lambda x:(-abs(x[1]-x[2])))
    answer = 0
    for i in range(n):
        ea = 0
        if info[i][1] <= info[i][2]:
            ea = min(info[i][0], a)
        elif info[i][1] > info[i][2]:
            ea = info[i][0] - min(info[i][0], b)
        answer += info[i][1]*ea + info[i][2]*(info[i][0]-ea)
        a -= ea
        b -= (info[i][0]-ea)
    print(answer)