풍선 (4716번) - 백준 (BOJ)

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

4716번: 풍선

 

백준 - 풍선 (Balloons) (4716번)

 

난이도 : Gold 1

알고리즘&자료구조 : Greedy (그리디) & Sorting (정렬)

시간복잡도(Time Complexity) : O( N*logN )

---

< 전체 코드 >

import sys
input = sys.stdin.readline


class Room():
    def __init__(self, balloons):
        self.balloons = balloons


class Teams():
    def __init__(self, arr):
        self.teams = arr
    

    def _sort(self):
        self.teams.sort(key=lambda x: x[1]-x[2])
    
    
    def _deliver(self, Room, idx, count):
        while self.teams:
            if Room.balloons >= self.teams[-1][0]:
                Room.balloons -= self.teams[-1][0]
                count += self.teams[-1][0] * self.teams[-1][idx]
                self.teams.pop()
            else:
                self.teams[-1][0] -= Room.balloons
                count += Room.balloons * self.teams[-1][idx]
                Room.balloons = 0
                break
        return count


if __name__ == '__main__':
    while True:
        N, A, B = map(int, input().split())
        if N == A == B == 0:
            break
        a, b = Room(A), Room(B)
        a_team, b_team = Teams([]), Teams([])
        for _ in range(N):
            K, Da, Db = map(int, input().split())
            if Db >= Da:
                a_team.teams.append([K, Db, Da])
            else:
                b_team.teams.append([K, Da, Db])
        a_team._sort()
        b_team._sort()
        count = a_team._deliver(a, 2, 0)
        count = b_team._deliver(b, 2, count)
        if a_team.teams:
            count = a_team._deliver(b, 1, count)
        elif b_team.teams:
            count = b_team._deliver(a, 1, count)
        print(count)

---

 

★ 핵심 Idea

어떤 방에서 A까지 거리와 B까지 거리 간의 차이가 클수록,

더 가까운 방의 풍선들을 먼저 가져다놓아야 한다. (Greedy)

 

 

 

① A까지 거리가 더 가까운 방들의 정보는 "a_team"에,

B까지 거리가 더 가까운 방들의 정보는 "b_team"에 나눠서 저장한다.

 

N, A, B = map(int, input().split())
if N == A == B == 0:
    break
a, b = Room(A), Room(B)
a_team, b_team = Teams([]), Teams([])
for _ in range(N):
    K, Da, Db = map(int, input().split())
    if Db >= Da:
        a_team.teams.append([K, Db, Da])
    else:
        b_team.teams.append([K, Da, Db])

 

 

② A까지 거리와 B까지 거리의 차이를 기준으로, 오름차순 정렬한다.

 

def _sort(self):
    self.teams.sort(key=lambda x: x[1]-x[2])
    
a_team._sort()
b_team._sort()

 

 

③ A와 거리가 더 가까운 방들을 모아둔 "a_team"에는 A에서 풍선을 가져오고,

B와 거리가 더 가까운 방들을 모아둔 "b_team"에는 B에서 풍선을 가져온다.

 

def _deliver(self, Room, idx, count):
    while self.teams:
        if Room.balloons >= self.teams[-1][0]:
            Room.balloons -= self.teams[-1][0]
            count += self.teams[-1][0] * self.teams[-1][idx]
            self.teams.pop()
        else:
            self.teams[-1][0] -= Room.balloons
            count += Room.balloons * self.teams[-1][idx]
            Room.balloons = 0
            break
    return count
    
count = a_team._deliver(a, 2, 0)
count = b_team._deliver(b, 2, count)

 

 

④ 만약 풍선이 모자라서 다 가져다놓지 못한 방이 있다면,

거리가 더 먼 반대편 방에서 필요한 풍선을 가져온다.

 

if a_team.teams:
    count = a_team._deliver(b, 1, count)
elif b_team.teams:
    count = b_team._deliver(a, 1, count)

 

 

⑤ 위 과정을 거쳐서 계산한 총 이동길이 "count"를 출력한다.

 

print(count)