백준 2180 (C++) 소방서의 고민

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

2180번: 소방서의 고민

문제 이해

문제의 입출력을 보자.

입력
3
2 0
1 2
0 3

출력
5

운이 좋게도 주어진 입력 예시 순서를 따라가면 출력이 나온다.
화재를 진압하는데 걸리는 시간은 at + b이므로

1번째 소방서에서 0초 소비, (2 * 0 + 0)

2번째 소방서에선 2초 소비, (1 * 0 + 2)

3번째 소방서에선 3초 소비 (0 * 2 + 3) 하므로

총 5초(정확히는 단위 시간) 이 소비된다.

 

 

 

 

 

수식화

i) a1, b1 ... ai, bi,    ai+1, bi+1 ... an, bn

를 최적해를 가정

이때 i번째 소방서에서 ti는 ai, bi 에 관한 1차 함수일 것이고, 그 식은

ai * ti + bi

i+1번째 소방서에서 시간 ti+1은

ti+1 = ti + ai ti + bi
따라서
ti+2 = ti + ai ti + bi + ( ti + ai ti + bi ) ai+1 + bi+1

이다.

 

 

ii) a1, b1 ... ai+1, bi+1,    ai, bi, ... an, bn

최적해가 아닌 다른 해일때

i+1번째 소방서에서 시간 ti+1은

ti+1 = ti + ai+1 ti + bi+1
따라서
ti+2' = ti + ai+1 ti + bi+1 + ( ti + ai+1 ti + bi+1 ) ai + bi

 

여기서 i)의 상황이 최적임을 가정했으므로 ti+2 <= ti+2' 이다.

이 부등식의 동항을 제거, 제거하다보면

ai​bi​​ ≤ ai+1​bi+1​​

일때 최적해라는 결과를 얻게 된다.

 

 

그리디 알고리즘

ai​bi​​ ≤ ai+1​bi+1​​ 가 최적해이다.

다만, a == 0 인 경우 화재 진압에 항상 b만큼의 시간이 걸린다는 것을 유의하자.

따라서 double b / a의 값이 큰 순서대로 정렬하고 조건에 맞게 총 시간을 더한다.

 

 

---

 

SMALL

 

 

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
const int MAX = 40000;
ll n, sum=0;
vector<tuple<double, int, int>> v;
vector<pair<int, int>> tail;

void print() {
    for (int i = 0; i < n; i++) {
        cout << get<0>(v[i]) << " " << get<1>(v[i]) << " " << get<2>(v[i]) << '\n';
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n;
    for (int i = 0; i < n; i++) {
        double a, b;
        cin >> a >> b;
        if (a == 0) {
            v.push_back(make_tuple(MAX, a, b));
        }
        else v.push_back(make_tuple(b/a, a, b));
    }
    sort(v.begin(), v.end());
   // print();
    
    int t = 0;
    for (int i = 0; i < n; i++) {
        sum += get<1>(v[i]) * t + get<2>(v[i]);
        sum %= 40000;
        t = sum;
    }
    cout << sum;
    return 0;
}

 

---