[BOJ 4716] 풍선

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

4716번: 풍선

 

- 문제 요약

 

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

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

어떤 팀은 방 A에 가깝고, 어떤 팀은 B에 더 가깝다. 

각 팀에게 달아줘야 하는 풍선의 수와 방 A와 B로부터의 거리가 주어진다.

이때, 모든 풍선을 달아주는데 필요한 이동 거리의 최솟값을 출력한다.

대회에서 풍선을 달아주는 사람은 매우 많고, 풍선은 한 가지 색상을 여러 개 달아준다고 가정한다.

풍선을 달기 위해 이동해야 하는 거리는 팀이 A와 B로부터 떨어진 거리와 같다.

풍선을 달아주는 사람은 한 번에 풍선 하나만 들고 이동할 수 있다.

 

 

- 알고리즘 정리

 

이동 거리를 최소로 만들어줘야 하므로 두 방의 거리차를 생각해 줍니다.

방 A와 방 B의 거리차가 클 수록 먼저 봐줘야 그리디 하게 문제를 해결할 수 있으므로 자동으로 정렬을 해주는 우선순위 큐를 사용해서 문제를 해결했습니다. (번호 매기는 느낌으로 pair<거리차,인덱스>)

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

#define MAX 1001
int n,a,b,k[MAX],da[MAX],db[MAX];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    while(true){
        priority_queue<pair<int,int> >pq;
        int result=0;
        cin>>n>>a>>b;
        if(n==0&&a==0&&b==0){
        	break;
		}
        for(int i=0;i<n;i++){
            cin>>k[i]>>da[i]>>db[i];
            pq.emplace(abs(da[i]-db[i]),i);
        }
        while(!pq.empty()){
            auto [cha,idx]=pq.top();
            pq.pop();
            int &flag=(da[idx]>db[idx]?b:a);
            if(flag){
                int mn=min(flag,k[idx]);
                flag-=mn;
                k[idx]-=mn;
                result+=mn*min(da[idx],db[idx]);
            }
            result+=max(da[idx],db[idx])*k[idx];
        }
        cout<<result<<'\n';
    }
}

코드 제출 결과

??? : 어디부터 잘못된걸까