소방서의 고민 [G1]

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

분류

• 그리디 알고리즘
• 정렬

✔ 풀이과정

화재 현장 진압순서가 무작위 상태일 때로 시작한다 가정해봅시다.
A 와 B가 순서상으로 붙어 있을 때 전체 화재 진압시간을 다음과 같이 쓸 수 있습니다.

전체 진압시간 = (A,B 이전 화재 진압시간) + (A,B 진압 시간) + (A,B 이후 화재 진압시간)

A, B를 어떤 순서로 진압하던 (A,B이전 화재 진압시간)에는 변화가 없습니다.
만약 (A, B 진압시간)을 단축 시킨다면 (A,B이후 화재 진압시간)은 항상 같거나 더 빠름이 보장됩니다.
그렇다면 연속해 있는 두 화재를 비교했을 때 어떤 순서로 배치하는 것이 더 이득인가를 알 수만 있다면 정렬 알고리즘으로 해결할 수 있을 것입니다.

A = at + b
B = ct + d
위의 식을 가지고 어떤 순서가 이득인지 계산해봅시다.
진압을 시작하는 시각을 T라고 합시다.

1. A B 순서로 진압 할 경우
   -A진압 할 때 aT + b 만큼 소요
   -B진압 할 때 c(aT + b + T) + d
   총 소요시간 = acT + bc + cT + d + aT + b
2. B A 순서로 진압 할 경우
   -B진압 할 때 cT + d 만큼 소요
   -A진압 할 때 a(cT + d + T) + b 만큼 소요
   총 소요시간 = acT + ad + aT + b +cT + d

1번 케이스 < 2번 케이스 라고 가정하고 부등식을 세워서 정리하면 다음 식이 나옵니다.
bc < ad
좀 더 의미 있게 바꿔보면
b/a < d/c

❗그렇습니다 두 화재간의 우선순위는 b/a로 손쉽게 비교가 가능합니다!!!!

그리고 경계케이스를 조심해야 합니다.
분모인 a 가 0 인경우는 제일 뒤로 보내는 예외처리를 해야하고, 비교를 하는 두 현장의 분자가 모두 0인 경우 a가 큰쪽을 더 앞으로 보내는 예외처리를 해야합니다.

이제 경계케이스를 조심하며 b/a로 정렬하고, 앞에서부터 차례대로 시간을 계산하면 됩니다.

코드에선 bc < ad로 정렬하였습니다.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n;
vector<pair<int, int>> fire;

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

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	int a, b;
	for (int i = 0; i < n; i++)
	{
		cin >> a >> b;
		fire.push_back(make_pair(a,b));
	}
	sort(fire.begin(), fire.end(), comp);
	int aa,bb;
	long long Time = 0;
	for (int i = 0; i < fire.size(); i++)
	{
		aa = fire[i].first;
		bb = fire[i].second;
		Time += Time * aa;
		Time += bb;
		Time %= 40000;
	}
	cout << Time;
	return 0;
}