[백준 / BOJ] C++ 4716 풍선

4716번: 풍선

 

문제

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

4716번: 풍선

 

 

풀이

각 팀에 필요한 풍선의 개수와 창고 A, B까지의 거리가 주어지면, 가장 효율적으로 창고에서 꺼내서 전달할 때 이동 거리를 구하는 문제다. 처음엔 각 팀이 주어질 때마다 A가 더 가까우면 A에서 양만큼 꺼내주고 충분하지 않으면 B에서 더 꺼내주도록 했다. 반대로 B가 더 가까울 때도 마찬가지. 그러나 틀렸습니다를 받았다.

 

다음으로 접근한 방법은 A와 B까지의 거리의 차가 클수록 가까운 창고에 남은 풍선이 부족할 때 더 많이 손해를 볼 것이다. 그래서 각 팀의 정보를 벡터에 저장한 다음 거리의 차가 큰 순서대로 정렬해 줬다. 그리고 앞에 썼던 로직을 그대로 사용했다. 마찬가지로 틀렸습니다를 받았다.

 

혼자 코드리뷰를 해보다 치명적인 실수를 발견했다. A가 더 가까울 때, A에 필요한 만큼 충분히 남아있진 않아도 조금이라도 남아있다면 그것부터 전달을 했어야한다! 수정하고 또 하나 발견한 실수는 범위 확인을 잘못했다. 풍선의 수 × 거리 = 1,000 × 10,000 이라 INT로 충분하다고 생각했는데 팀의 수도 최대 1,000이라 INT 범위를 벗어난다. 그래서 출력값인 ans를 long long으로 바꿔줬다.

 

 

코드

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

struct team {
  // 팀에 필요한 풍선 개수, A까지 거리, B까지 거리
  int K, a, b;
};

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  while (1) {
    int N, A, B;
    long long ans = 0; // 1,000×10,000×1,000은 INT 범위 초과
    cin >> N >> A >> B;
    if (!N && !A && !B)
      break;
      
    // 각 팀의 정보 저장
    vector<team> v(N);
    for (int i = 0; i < N; i++)
      cin >> v[i].K >> v[i].a >> v[i].b;
      
    // A와 B까지의 거리의 차가 큰 순서로 정렬
    sort(v.begin(), v.end(), [](team a, team b) { return abs(a.a - a.b) > abs(b.a - b.b); });
    
    // 거리의 차가 큰 것부터
    for (int i = 0; i < N; i++) {
      int K = v[i].K, a = v[i].a, b = v[i].b;
      if (a<b) { // A까지 거리가 더 짧을 때
        if (A >= K) { // A에 충분히 풍선이 남아있으면
          ans += K * a; // 풍선 개수×거리만큼 증가
          A -= K; // 풍선 K개 제거
        } else { // A에 풍선이 충분하지 않다면
          // A에 남은 풍선부터 전달
          ans += A * a;
          K -= A;
          A = 0;
          // 남은 양만큼 B에서 전달
          ans += K * b;
          B -= K;
        }
      } else { // 위와 로직은 같음
        if (B >= K) {
          ans += K * b;
          B -= K;
        } else {
          ans += B * b;
          K -= B;
          B = 0;
          ans += K * a;
          A -= K;
        }
      }
    }
    cout << ans << '\n';
  }
  return 0;
}