BOJ 4716 : 풍선

3줄요약

그리디

정렬

구현

 

 

서론

 

하고 싶은 얘기는 없다.

 

 

본론

 

이 문제는 그리디로 풀 수 있다. 사람의 수도 아닌, A 혹은 B에서 떨어진 거리에 대하여 정렬하지 않고, A와 B의 거리의 차가 큰 순서대로 정렬한다. 그리고 정렬한 배열의 i = 0~N-1 에 대해 다음의 4가지 경우를 생각한다.

 

만약 a가 더 크다면, 그리고 지금 있는 풍선 수로 i번째 인덱스의 팀의 사람들을 충당할 수 있을 때의 경우

a가 더 크지만 지금 있는 풍선 수로 팀의 사람들을 충당할 수 없을 때의 경우

b가 더 크고, 지금 있는 풍선 수로 팀의 사람들을 충당할 수 있을 때의 경우

b가 더 크지만, 지금 있는 풍선 수로 팀의 사람들을 충당할 수 없을 때의 경우

 

이 경우들에 대해 각각 알맞은 처리를 하면 된다. 코드는 밑에 있다.

 

 

#include <iostream>
#include <vector>
#include <math.h>
#include <algorithm>

using namespace std;

bool cmp(pair<int, int> left, pair<int, int> right) {
    if (left.first == right.first) return left.second > right.second;
    else return left.first > right.first;
}

void solve(int N, int ba, int bb) {

    int person[1001], dista[1001], distb[1001];
    pair<int, int> distsub[1001];

    for (int i = 1; i <= N; i++) {
        cin >> person[i] >> dista[i] >> distb[i];
        distsub[i - 1] = { abs(dista[i] - distb[i]), i };
    }

    sort(distsub, distsub + N, cmp);

    int ans = 0;
    for (int i = 0; i < N; i++) {
        int idx = distsub[i].second;
        int da = dista[idx]; int db = distb[idx]; int p = person[idx];

        if (da <= db) {
            if (ba > p) {
                ans += p * da;
                ba -= p;
            } else {
                ans += da * ba;
                int c = p - ba;
                ba = 0;
                ans += c * db;
                bb -= c;
            }
        }
        else {
            if (bb > p) {
                ans += p * db;
                bb -= p;
            } else {
                ans += db * bb;
                int c = p - bb;
                bb = 0;
                ans += c * da;
                da -= c;
            }
        }
    }

    cout << ans << endl;
}

int main() {
    
    while (true) {
        int N, ba, bb; cin >> N >> ba >> bb;
        if (N == 0 && ba == 0 && bb == 0) break;
        
        solve(N, ba, bb);
    }
}

 

결론

 

코로나 걸렸는데 문제를 푸는 나에 대해 약간의 자괴감을 느낀다.

 

난이도(개인적): Gold II

난이도(객관적): Gold I