[BOJ/Python] 4716번 문제풀이

문제 설명

전대프연 대회에서 문제를 푼 팀은 풍선을 받게 된다. 풍선은 사람이 직접 달아주기 때문에 자원 봉사자가 필요하다.

풍선은 방 A와 방 B에 보관되어 있다. 대회에 참가한 팀의 수는 총 N개이고, 앉아있는 자리는 서로 다르다. 어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다.

각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다. 이때, 모든 풍선을 달아주는데 필요한 이동 거리의 최솟값을 출력한다. 대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다. 풍선을 달기 위해 이동해야하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다. 풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스의 첫째 줄에는 팀의 수 N(1 ≤ N ≤ 1,000)과 방 A와 B에 보관되어있는 풍선의 수 A, B가 주어진다. (0 ≤ A, B ≤ 10,000)

다음 N개 줄에는 팀에게 달아줘야하는 풍선의 수 K와 방 A로부터 떨어진 거리 DA, B로부터 떨어진 거리 DB (0 ≤ DA, DB ≤ 1,000)가 주어진다. 풍선이 부족한 경우는 없다. 즉, Σi Ki ≤ A+B.

입력의 마지막 줄에는 0이 세 개 주어진다.

출력

각 테스트 케이스에 대해서, 모든 팀에게 풍선을 달아주기 위해 필요한 이동 거리의 최솟값을 한 줄에 하나씩 출력한다. 이때, 풍선을 달아주고 방 A나 B로 돌아오는 거리는 포함하지 않는다. 즉, 방 A와 B에서 팀으로 이동하는 거리만 포함한다.

---

풀이 과정

이 문제의 접근 과정은 다음과 같다.

1. 각 자리에 대한 정보를 리스트로 입력받는다.
2. 각 앉아있는 자리마다 A와 B 방의 거리를 기준으로 내림차순 정렬한다
3. 리스트를 하나씩 뽑으면서 풍선의 개수와 이동거리를 비교하며 최종적으로 이동한 거리를 출력한다. (단, 이동 거리가 같은 경우는 우선순위를 가장 뒤로 미룬다.)

 

따라서 방 A 거리와 방 B 거리의 차이값을 내림차순으로 정렬하고 A 방과 B 방 중 어느 방이 더 가까운지 판단해서 우선적으로 풍선을 분배해주면 이동 거리의 최솟값을 출력할 수 있었다.

 

해당 문제에 사용되는 알고리즘 ➡️ 그리디 (Greedy) 알고리즘

[관련 자료]

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/

 

while True:
    n, a, b = map(int, input().split())
    if n == a == b == 0:
        break
    array = [list(map(int, input().split())) for _ in range(n)]
    array.sort(key=lambda x: abs(x[1] - x[2]), reverse = True)
    total_distance = 0
    equal_dis = []
    for ballon, distanceA, distanceB in array:
        if distanceA > distanceB:
            if b >= ballon:
                b -= ballon
                total_distance += distanceB * ballon
            else:
                ballon -= b
                total_distance += distanceB * b
                b = 0
                total_distance += distanceA * ballon
        elif distanceA < distanceB:
            if a >= ballon:
                a -= ballon
                total_distance += distanceA * ballon
            else:
                ballon -= a
                total_distance += distanceA * a
                a = 0
                total_distance += distanceB * ballon
        else:
            equal_dis.append([ballon, distanceA, distanceB])
    
    for i in range(len(equal_dis)):
        total_distance += equal_dis[i][0] * equal_dis[i][1]
    
    print(total_distance)

 

 

[참고자료]

https://velog.io/@shinjy9802/%EB%B0%B1%EC%A4%80-4716%EB%B2%88-%ED%92%8D%EC%84%A0-Java

https://konghana01.tistory.com/263