[BOJ 4716, Python 3] 풍선

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

4716번: 풍선

 

풀이

이 문제는 입력된 순서대로 풍선을 주는 것이 아니니 정렬해볼 수 있다는 것을 생각해볼 수 있습니다.

거기다가 매 선택마다 최적해를 선택해야하니 각 팀마다 A와 B중 하나에 몰아넣을 수 있을 수 있겠네요. 그러면 경우의 수가 3가지로 나옵니다.

1. A와 B중 최솟값을 기준으로 오름차순하여 값이 작은 풍선부터 줌

2. A와 B중 최댓값을 기준으로 내림차순하여 값이 작은 풍선부터 줌

3. A와 B 차이를 기준으로 내림차순하여 값이 작은 풍선부터 줌

 

1. A와 B중 최솟값을 기준으로 오름차순

2 10 10

10 1 50

10 10 100

인 입력값이 있다고 해보면 1팀이 A번 풍선을 다가지고, 2팀이 B번 풍선을 다가져서 1010이 나옵니다. 근데 이건 600이 정답입니다.

 

2. A와 B중 최댓값을 기준으로 내림차순

여기서는 최솟값을 오름차순하냐, 내림차순하냐로 나눌 수 있는데 내림차순이 틀렸다는 반례를 찾을 수 있습니다.

3 15 15

10 1 100

10 20 60

10 1 50

를 하면 1팀 A 10개, 2팀 A 5개, B 5개, 3팀 B 10개로 10 + 100 + 300 + 500 = 910으로 나오지만

정답은 1팀 A 10개, 2팀 B 10개, 3팀 A 5개, B 5개로 10 + 600 + 5 + 250 = 765가 정답입니다.

 

참고로 저는 여기서 A와 B의 차이를 기준으로 내림차순하여 작은 값에  전부 몰아주는 것을 깨달았습니다.

 

3. A와 B 차이를 기준으로 내림차순하여 값이 작은 풍선부터 줌

문제를 보면 풍선이 부족한 경우는 없다고 합니다. 이 말은 모든 팀에게 풍선을 줄 수 있다는 것입니다.

풍선은 A와 B 둘 중 하나를 무조건 줄 수 있으므로 A와 B사이의 거리가 큰 것부터 줘야한다는 것을 알 수 있게 됩니다.

 

 

 

옛날 통과 코드를 보니까 에드몬드 카프 알고리즘으로 풀었는데, 그리디가 생각나지 않으면 참 힘들 것 같네요

코드

while 1:
    n, a, b = map(int, input().split())
    if n == a == b == 0: break
    arr = sorted([[*map(int, input().split())]for _ in range(n)], key=lambda x: -abs(x[1]-x[2]))
    ans = 0
    for k, x, y in arr:
        if x <= y: val = min(k, a)
        else: val = k - min(k, b)
        ans += val * x + (k - val) * y
        a -= val
        b -= k - val
    print(ans)