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

문제

2180번: 소방서의 고민

n개의 화재가 발생하고 소방수가 최소의 시간으로 화재를 진압하는 시간을 구하는 문제입니다.

화재를 진압하는 시간은 a * t + b로 n개의 a, b가 주어지고 t는 항상 0부터 시작합니다.

예를 들어 n이 3이고 a, b가 (2, 0), (1, 2), (0, 3) 이렇게 주어지면 최소시간은 5 입니다.

(2 * t0 + 0) + (1 * t1 + 2) + (0 * t2 + 3)

=5 

 

우리는 화재를 최대한 빠르게 진압해야 하므로 어느 조건으로 화재를 진압해야 빨리 화재가 진압되는지

알아 내야 합니다.

즉 최적해를 구해야 합니다.

예를 들어 다음과 같은 n개의 화재가 있다고 하면 t(i+2)를 구하는 방법을 보겠습니다.

t(i+2) = t(i) + a(i)*t(i) + b(i) + a(i+1)*(t(i) + a(i)*t(i) + b(i)) + b(i+1) 입니다.

 

반대로 최적해가 아닌 경우 즉, 아무렇게나 화재를 진압할 경우를 보겠습니다.

t(i+2)' =t(i) + a(i+1)*t(i) + b(i+1) + a(i)*(t(i) + a(i+1)*t(i) + b(i+1)) + b(i) 입니다.

 

결로부터 보자면 t(i+2)는 항상 t(i+2)' 보다 작거나 같아야 합니다. 왜냐하면 t(i+2)이 t(i+1)' 보다 커져버리면 

결국 시간이 계속 축적되어 마지막에 시간이 더 오래걸린채로 남아있기 때문입니다.

결국 시간은 계속 흐르기 때문에 앞에서 최소한의 시간을 할애 해야 마지막에 시간이 최소가 됩니다. 

따라서 t(i+2) <= t(i+2)' 이기 때문에 식을 간소화 하면

t(i) + a(i)*t(i) + b(i) + a(i+1)*(t(i) + a(i)*t(i) + b(i)) + b(i+1)

≤ t(i) + a(i+1)*t(i) + b(i+1) + a(i)*(t(i) + a(i+1)*t(i) + b(i+1)) + b(i)

중복된 식을 다 제거하면

b(i)*a(i+1) ≤ b(i+1)*a(i) 입니다.

식을 좀더 간소화 하면 다음과 같습니다.

하지만 이러한 식은 a가 0일 때는 불가능한 식입니다.

a가 0일 때는 항상 b만큼의 시간이 걸립니다. 

따라서 a = 0일 때는 어느 차례에서나 항상 시간이 b값이 되므로 맨 마지막에 불을 꺼도 상관이 없습니다.

결국에는 a가 0일 때는 제외하고 위의 식이 성립하게 됩니다.

 

즉, a를 계속 보다가 0이 나오면 그냥 맨 뒤로 보내줍니다.

또한 만약 a의 어느 구간이

이러면 두 수의 위치를 서로 바꿔주면 최적해와 유사하게 진행됩니다.

 

따라서 우리는 먼저 a와 b를 입력받은 배열을 알맞은 조건에 맞게 정렬해주어야 합니다.

bool cmm(pair<int,int> a, pair<int,int> b) {
	if (a.first == 0)return false;
	else if (b.first == 0)return true;
	else if (a.second == 0 && b.second == 0)return a.first < b.first;
	return a.second * b.first < a.first* b.second;
}

정렬 함수입니다.

int time = 0;
	for (int i = 0; i < v.size(); i++) {
		time = time+time * v[i].first + v[i].second;
		time %= 40000;
	}

시간을 계산하는 코드입니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
#define inf INT_MAX
using namespace std;
using ll = long long;
using ull = unsigned long long;
bool cmm(pair<int, int> a, pair<int, int> b);
vector<pair<int, int>>v;
int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	int n;
	cin >> n;
	for (int i = 0,a,b; i < n; i++) {
		cin >> a >> b;
		v.push_back({ a,b });
	}
	sort(v.begin(), v.end(), cmm);
	int time = 0;
	for (int i = 0; i < v.size(); i++) {
		time = time+time * v[i].first + v[i].second;
		time %= 40000;
	}
	cout << time;
	return 0;
}
bool cmm(pair<int,int> a, pair<int,int> b) {
	if (a.first == 0)return false;
	else if (b.first == 0)return true;
	else if (a.second == 0 && b.second == 0)return a.first < b.first;
	return a.second * b.first < a.first* b.second;
}