📚 4716 - 풍선

풍선

이해

N : 팀의 수
방 A, B에 보관되어있는 풍선의 수 : A, B

N개의 줄에는 팀에게 달아줘야하는 풍선의 수 K, 방 A로부터 떨어진 거리 Da, B로부터 떨어진 거리 Db가 주어진다.

모든 팀에게 풍선을 달아주기 위해 필요한 이동 거리의 최솟값을 한 줄에 출력한다.

A방에서 가져올 풍선을 B방을 선택해서 이득을 보거나 B방에서 가져올 풍선을 A방을 선택해서 이득을 봐야한다.
두 방의 거리차가 클수록 먼저 고려해서 풍선을 이동시켜 해당 팀부터 풍선을 배부해야 한다.

ex) 40, 10이 있을 때 10인 방을 이용해서 풍선을 전달해야 거리가 40인 방의 풍선을 전달받지 않아 최소의 답을 구할 수 있다.

a가 더 가까울 때 
- A에 있는 풍선으로 전부 해결 안될 때는
  - A에 있는 풍선 다쓰고 B에 있는 풍선을 사용한다.
- A에 있는 풍선을 전부 해결될 때

b가 더 가까울 때
- B에 있는 풍선으로 전부 해결 안될 때는
  - B에 있는 풍선 다쓰고 A에 있는 풍선을 사용한다.
- B에 있는 풍선을 전부 해결될 때  

소스

import sys  
  
input = sys.stdin.readline  
  
while True:  
    # input  
    N, A, B = map(int, input().rstrip().split())  
    if N == 0:  
        break  
  
    q = []  
    # 거리 계산  
    for _ in range(N):  
        K, D1, D2 = map(int, input().rstrip().split())  
        diff = abs(D1 - D2)  
        q.append((diff, K, D1, D2))  
    q.sort()  
    result = 0  
    for _ in range(N):  
        dumb, K, D1, D2 = q.pop()  
        # A로 가는 경우  
        if D1 <= D2:  
            # A가 충분한 경우  
            if K <= A:  
                result += D1 * K  
                A -= K  
            # A가 부족한 경우  
            else:  
                # 남아있는 A를 모두 사용  
                result += D1 * A  
                left = (K - A)  
                A = 0  
                # 부족한만큼 B를 사용
					 # k는 A + B 보다 작거나 같다.
                result += left * D2  
                B -= left  
        # B로 가는 경우  
        else:  
            # B가 충분한 경우  
            if K <= B:  
                result += D2 * K  
                B -= K  
            # B가 부족한 경우  
            else:  
                # 남아있는 B를 모두 사용  
                result += D2 * B  
                left = (K - B)  
                B = 0  
                # 부족한만큼 A를 사용  
                result += left * D1  
                A -= left  
    print(result)

이번 문제도 생각보다 정렬하는데 있어 이해하는데 상당히 많은 시간이 들었던 것 같다.

참고 : https://3juhwan.tistory.com/6