[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)
댓글남기기