[BOJ][Python] 백준 4716 번: 기업투자

1일 1PS 84일차!

📚 문제

---

[골드 1] - 풍선

💡 풀이 과정

---

• 처음에는 A, B 팀 거리의 최솟값을 기준으로 오름차순 정렬을 하려 했다.

3 20 10
10 20 10
10 10 30
10 40 10
0 0 0

• 기존 테스트 케이스를 조금만 바꿔도 문제가 발생한다는 것을 쉽게 알 수 있다.
• 최솟값을 기준으로 오름차순 정렬 시 총 600 의 거리가 발생한다.
  • 1번팀 B 10개 (100)
  • 2번팀 A 10개 (100)
  • 3번팀 A 10개 (400)
• 하지만 정답은 400 이다.
  • 3번팀 B 10개 (100)
  • 2번팀 A 10개 (100)
  • 1번팀 A 20개 (200)
• 실제 정답 도출 과정에서 살펴보면 3번팀을 우선 배치한 것을 알 수 있는데, 이는 A 와 B 의 차이가 가장 크기 때문이다.
  • 다시 말하면 B 를 골라야하는데, A 를 고르면 가장 큰 손해가 발생한다는 뜻이다.
• 모든 팀은 결국 풍선을 골라야하기에 잘못 고르면 큰일나는 팀을 우선적으로 풍선을 고르게 하자는 발상이다.
  • teams.sort(key= lambda x : -1 * (abs(x[1]- x[2])))
  • 두 거리의 차를 기준으로 정렬한다.
  • 내림차순 정렬을 위해 -1 을 곱해주었다.

📌포인트

---

• 입력
  • 처음 보는 유형의 입력이다. 조건에 맞춰 잘 처리하자.
• if문
  • A, B 중 어떤 팀이 가깝냐?
  • 해당 팀의 풍선이 남아있는가?
  • 많은 분기가 존재할 수 있다.
  • 하지만 모든 분기에 대해 balloon 이라는 변수에 A 팀에서 사용할 풍선의 수를 저장하므로써 후속 작업을 동일하게 처리할 수 있다.

💻 코드

---

import sys

while True:
    N, A, B = map(int, sys.stdin.readline().split())

    # 종료 조건
    if N == A == B == 0:
        break

    # A, B 팀 거리의 차가 큰 순서대로 정렬
    teams = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
    teams.sort(key= lambda x : -1 * (abs(x[1]- x[2])))

    result = 0
    for team in teams:
        # A 를 선택할 때
        if team[1] < team[2]:
            balloon = min(team[0], A)
        # B 를 선택할 때
        else:
            balloon = team[0] - min(team[0], B)

        # balloon = A 팀에서 가져올 수 있는 풍선의 수
        result += balloon * team[1] + (team[0] - balloon) * team[2]

        A -= balloon
        B -= team[0] - balloon


    print(result)