[BOJ/Platinum 5] 백준 17377 Taxi(C++)

문제 링크

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

17377번: Taxi

첫 줄에 정수 A, B, C가 입력되며, 각각 택시의 연료 용량, 승객이 1마일당 지불하는 돈, 1갤런당 갈 수 있는 거리이다. (1 ≤ A ≤ 100, 1 ≤ B ≤ 100, 1 ≤ C ≤ 100) 다음 줄에 지점의 개수 N이 입력된다.

www.acmicpc.net

문제

Taxi는 프로그래밍 언어로, 가상의 도시에서 택시가 이동하면서 승객을 태우는 과정으로 코드가 표현된다는 점이 특징이다. 이 도시의 지도는 다음과 같다.

(image from https://bigzaphod.github.io/Taxi/ )

이 언어로 "Hello, world!"를 출력하는 프로그램을 작성하면 다음과 같다.

"Hello, World!" is waiting at the Writer's Depot.
Go to Writer's Depot: west 1st left, 2nd right, 1st left, 2nd left.
Pickup a passenger going to the Post Office.
Go to the Post Office: north 1st right, 2nd right, 1st left.
Go to the Taxi Garage: north 1st right, 1st left, 1st right.

택시는 항상 Taxi Garage에서 출발하고, 프로그램 종료 시에도 이곳에 있어야 하며 이때 타고 있는 승객이 없어야 한다. 택시는 연료 A갤런을 채울 수 있으며, 처음 출발할 때는 연료가 가득 찬 상태이다. 각 지점에서는 특정 목적지로 가려는 승객을 태울 수 있고, 이 승객은 택시가 목적지에 도착하면 즉시 내린다. 이때 승객은 택시를 타고 이동한 거리 당 B원을 지불한다. 또한 택시는 승차 정원이 있기 때문에 승객은 최대 세 명까지만 태울 수 있다.

(원래의 설정과는 다르지만) 계산의 편의를 위해 이 도시에는 1마일 간격으로 수평 및 수직 도로가 있으며, 모든 지점은 두 도로가 만나는 지점에만 있다고 가정하자. 그러면 모든 지점은 정수 좌표로 나타낼 수 있으며, 두 지점 간의 거리는 맨해튼 거리(Manhattan distance)로 계산할 수 있다. 즉, 두 지점의 좌표가 (x1, y1), (x2, y2)일 경우 거리는 |x1 - x2| + |y1 - y2|이다. 단, 택시가 주행 중 특정 지점을 지나더라도 그 지점이 목적지인 승객이 내릴 수는 없으며, 정확히 목적지에 도착해야만 승객이 내릴 수 있다.

택시는 1갤런당 C마일을 갈 수 있는데, 주행 도중 연료가 떨어지면 안 된다. 도시에는 주유소가 세 곳 있다. 따라서 주행을 계속하기 위해 연료가 0 미만이 되기 전에 주유소에서 연료를 충전해야 한다. 입력되는 지점 중 세 곳은 주유소로, 이곳에 도착하면 자동으로 연료를 채우며, 세 주유소의 연료 1갤런당 가격은 다를 수 있다. 연료를 가득 채울 만큼의 돈이 있다면 그만큼을 지불하고 연료를 가득 채우고, 그렇지 않다면 가지고 있는 모든 돈을 지불하여 연료를 채운다. 연료를 가득 채우기 위해 필요한 돈이 정수로 나누어떨어지지 않는 경우 소수점 이하는 절사한다. 즉, 연료를 가득 채우기 위해 1,234.567...원이 필요한데 현재 1,234원 이상이 있을 경우 1,234원을 지불하고 연료를 가득 채운다. 만약 주유소가 목적지인 승객이 있다면 승객이 먼저 내리면서 요금을 지불한 후 연료를 채운다.

이제 이 명세를 바탕으로, 도시의 정보와 택시의 이동 경로가 주어졌을 때 택시가 모든 규칙을 만족하면서 운행을 완료하는지를 판단하는 프로그램을 작성해보자.

입력

첫 줄에 정수 A, B, C가 입력되며, 각각 택시의 연료 용량, 승객이 1마일당 지불하는 돈, 1갤런당 갈 수 있는 거리이다. (1 ≤ A ≤ 100, 1 ≤ B ≤ 100, 1 ≤ C ≤ 100)

다음 줄에 지점의 개수 N이 입력된다. (4 ≤ N ≤ 100)

이후 N줄에 걸쳐 i번째 지점의 이름 Di와 정수 좌표 xi, yi가 입력된다. (0 ≤ xi, yi ≤ 100) 이름에 들어갈 수 있는 문자는 알파벳과 아포스트로피('), 공백이다. 이름은 1글자 이상 30글자 이하로, 첫 글자와 마지막 글자는 공백이 될 수 없으며, 공백이 두 번 이상 연속한 경우도 없다. 모든 지점의 이름은 다르며, 이름이 Taxi Garage인 지점은 항상 존재한다. 이름에 들어가는 알파벳은 대소문자를 구분한다.

이후 세 줄에 걸쳐 주유소의 이름 Gi와 갤런당 가격 Pi가 입력된다. 세 주유소의 이름은 모두 다르며, 각각 앞에서 입력된 지점 중 하나이다. 갤런당 가격은 1 이상 100 이하의 정수이다. Taxi Garage는 주유소가 될 수 없다.

다음으로 문장의 개수 K가 입력된다. (1 ≤ K ≤ 10,000)

이후 K줄에 걸쳐 문장이 입력되며, 다음 두 형식 중 하나이다.

Go to (X).: X로 이동한다. X는 입력된 지점 중 하나이다.
Pickup a passenger going to (X).: X로 이동하는 승객을 태운다. X는 입력된 지점 중 하나로, 택시가 현재 위치한 지점과 Taxi Garage는 목적지가 될 수 없다.

출력

규칙에 맞게 운행을 완료한 경우, 최종적으로 번 돈의 액수를 출력한다.

운행에 실패한 경우, 다음 문자열 중 하나를 출력한다.

OUT OF GAS: 이동 중 연료가 떨어졌을 때
CAPACITY FULL: 정원보다 많은 승객을 태우려고 할 때
NOT IN GARAGE: 마지막 지점이 Taxi Garage가 아닐 때
REMAINING PASSENGER: 마지막 지점이 Taxi Garage이지만 아직 내리지 못한 승객이 있을 때

예제 입력 1

50 20 10
5
Taxi Garage 50 50
Zoom Zoom 13 66
Fueler Up 39 27
What's The Difference 95 32
Go More 2 34
Fueler Up 55
Go More 33
Zoom Zoom 17
7
Go to Go More.
Pickup a passenger going to Fueler Up.
Go to Zoom Zoom.
Go to Fueler Up.
Go to What's The Difference.
Go to Go More.
Go to Taxi Garage.

예제 출력 1

각 문장을 처리한 다음 택시의 상태는 다음과 같다. 처음에는 연료 50갤런, 돈 0원으로 시작한다.

Go to Go More.: Taxi Garage에서 64마일 이동한다. 연료는 6.4갤런 소비한다. 주유소이지만 돈이 없으므로 연료를 채우지 않는다. (43.6갤런/0원)
Pickup a passenger going to Fueler Up.: Fueler Up으로 가는 승객을 태운다. (43.6갤런/0원)
Go to Zoom Zoom.: 43마일 이동하면서 연료는 4.3갤런 소비한다. 역시 연료를 채우지 않는다. (39.3갤런/0원)
Go to Fueler Up.: 65마일 이동한다. 승객이 내리면서 2160원을 지불한다. 연료를 가득 채우기 위해 17.2*55=946원이 필요하므로 이를 지불하고 연료를 가득 채운다. (50갤런/1214원)
Go to What's The Difference.: 61마일 이동한다. (43.9갤런/1214원)
Go to Go More.: 95마일 이동한다. 연료를 가득 채우기 위해 15.6*33=514원(원단위 절사)이 필요하므로 이를 지불하고 연료를 가득 채운다. (50갤런/700원)
Go to Taxi Garage.: 64마일 이동한다. (43.6갤런/700원)

이동 중 연료가 떨어지거나 정원을 초과한 적이 없고, 마지막으로 Taxi Garage에 있으며 아직 내리지 않은 승객이 없으므로 번 돈의 액수인 700을 출력하면 된다.

예제 입력 2

10 20 10
4
Zoom Zoom 30 40
Fueler Up 100 0
Taxi Garage 0 0
Go More 0 100
Go More 40
Zoom Zoom 50
Fueler Up 60
3
Go to Go More.
Go to Fueler Up.
Go to Taxi Garage.

예제 출력 2

OUT OF GAS

예제 입력 3

30 40 50
5
Station A 0 0
Station B 10 10
Taxi Garage 20 20
Station C 30 30
KonKat's 40 40
Station A 10
Station B 10
Station C 10
8
Go to Station A.
Pickup a passenger going to KonKat's.
Go to Station B.
Pickup a passenger going to KonKat's.
Pickup a passenger going to Station A.
Go to Station C.
Pickup a passenger going to KonKat's.
Go to Taxi Garage.

예제 출력 3

CAPACITY FULL

예제 입력 4

30 30 30
4
Taxi Garage 1 2
A 3 4
B 5 6
C 7 8
A 10
B 20
C 30
1
Go to A.

예제 출력 4

NOT IN GARAGE

예제 입력 5

30 30 30
4
Taxi Garage 1 2
A 3 4
B 5 6
C 7 8
A 10
B 20
C 30
3
Go to A.
Pickup a passenger going to B.
Go to Taxi Garage.

예제 출력 5

REMAINING PASSENGER

알고리즘 분류

구현
문자열
파싱

풀이

우선 문자열 관리에 주의한다.

또한 나눗셈 과정에서 약간의 오차가 발생하는데, 이것을 위하여 미세한 수치만큼을 나눗셈 이후 더해준다.(1e-12 : 1 * 10^-12)

이것만 유의해주면 주어진 조건대로 구현해주는 것은 문제없다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <set>
#include <unordered_map>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define FIRST cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 10005
#define LL long long
#define LD long double
#define INF 1e9


using namespace std;
/*
	택시의 정보, 지점들의 정보, 승객들의 정보를 담는 구조체를 생성
*/
struct TAXI {
	LD Fuel;
	LL Money = 0;
};

struct PASSENGER {
	string Dest;
	LL Len;
};

struct INFO {
	int IDX; // 지점의 번호(없어도 됨)
	string D; // 지점의 이름
	LL Y, X; // 지점의 좌표
	bool isGarage = false; // 주유소라면 true, 아니라면 false(주유소 영어로 뭔지 모름)
	LL P = 0; // 주유소라면 연료 1갤런당 가격은 0이 아니고, 주유소가 아니라면 0
};

int A, B, C, N, K;
string STR, CMD;
TAXI Taxi;
pair<LL, LL> Taxi_Pos;
pair<LL, LL> Taxi_Garage_Pos;
vector<INFO> Point;
vector<PASSENGER> Passenger;
unordered_map<string, LL> UM;

int main() {
	FIRST
	cin >> A >> B >> C;
	Taxi.Fuel = A;
	cin >> N;
	/*
		cin을 사용하면 띄어쓰기를 하는 즉시 string의 입력이 종료된다.
		따라서 getline을 사용해서 지점들의 이름, 좌표를 한꺼번에 입력받도록 한다.
	*/
	getline(cin, STR);
	for (int i = 0; i < N; i++) {
		INFO Info;
		Info.IDX = i + 1;
		int Number_IDX = 0;
		getline(cin, STR);
		for (int j = 0; j < STR.size(); j++) {
			if ((STR[j] >= '0') && (STR[j] <= '9')) {
				// 숫자가 나오면 지점의 이름을 다 입력받은 것이므로
				Info.D = STR.substr(0, j - 1);
				Number_IDX = j;
				break;
			}
		}
		string Number = "";
		for (int j = Number_IDX; j < STR.size(); j++) {
			if (STR[j] == ' ') { // 숫자 뒤에 띄어쓰기가 나왔다면 띄어쓰기가 나오기 전의 숫자는 X좌표
				Info.Y = stoi(Number);
				Number_IDX = j + 1;
				break;
			}
			Number += STR[j];
		}
		Info.X = stoi(STR.substr(Number_IDX)); // 띄어쓰기가 나온 후의 숫자는 Y좌표
		if (Info.D == "Taxi Garage") {
			// 처음은 Taxi Garage에서 시작하므로 Taxi Garage의 좌표를 시작지점으로 하고, 다시 돌아와야 하므로 최종 목적지 역서 Taxi Garage로 지정한다.
			Taxi_Pos = make_pair(Info.Y, Info.X);
			Taxi_Garage_Pos = make_pair(Info.Y, Info.X);
		}
		Point.push_back(Info);
		UM.insert(make_pair(Info.D, i));
	}
	for (int i = 0; i < 3; i++) {
		string STR;
		string STR2 = "";
		int Number_IDX = 0;
		getline(cin, STR);
		for (int j = 0; j < STR.size(); j++) {
			if ((STR[j] >= '0') && (STR[j] <= '9')) {
				STR2 = STR.substr(0, j - 1);
				Number_IDX = j;
				break;
			}
		}
		/*
			반복문을 사용해서 주유소로 지정된 지점을 찾는 방법 대신
			map을 사용해서 지점을 주유소로 바꾸도록 해서 코드의 길이를 줄였다.
		*/
		Point[UM[STR2]].isGarage = true;
		Point[UM[STR2]].P = stoi(STR.substr(Number_IDX));
	}
	cin >> K;
	getline(cin, CMD);
	for (int i = 0; i < K; i++) {
		getline(cin, CMD);
		int Len = CMD.size();
		CMD = CMD.substr(0, Len - 1);
		if (CMD.substr(0, 6) == "Go to ") { // 문장의 앞이 Go to로 시작한다면
			string Dest = CMD.substr(6); // Go to 다음의 문자열이 목적지다.
			int Move_Len = abs(Taxi_Pos.first - Point[UM[Dest]].Y) + abs(Taxi_Pos.second - Point[UM[Dest]].X);
			 // 맨해튼 거리를 통한 현재 택시의 지점과 목적지의 지점 간의 거리를 계산
			LD Used_Fuel = (LD)Move_Len / C;
			// 나눠질 때 우리가 원래 알고 있던 값과는 약간의 오차가 존재한다.
			Taxi.Fuel -= Used_Fuel;
			Taxi_Pos = make_pair(Point[UM[Dest]].Y, Point[UM[Dest]].X);
			if (Taxi.Fuel < -1e-12) { // OUT OF GAS : 이동 중 연료가 떨어졌을 때
				// 1e-12(10의 -12제곱, 즉 엄청나게 작은 수), 실수 오차 문제를 해결하기 위해 사용
				cout << "OUT OF GAS" << "\n";
				return 0;
			}
			for (int j = 0; j < Passenger.size(); j++) {
				Passenger[j].Len += Move_Len; // 탑승객들이 이동한 거리를 증가
				if (Passenger[j].Dest == Dest) { // 목적지에 도착했다면 이동해온 거리 * B만큼의 비용을 택시에게 지불 후 하차
					Taxi.Money += (Passenger[j].Len * B);
					Passenger.erase(Passenger.begin() + j);
					j--;
				}
			}
			if (Point[UM[Dest]].isGarage) { // 목적지가 주유소라면
				LL Price = Point[UM[Dest]].P;
				LD Diff = A - Taxi.Fuel;
				Diff = max(Diff, (LD)0.0); // 연료 용량과 현재 남은 연료의 차이
				LD Must_Pay = (LD)Price * Diff; // 그 차이 * 주유소의 가격 = 주유소에 지불해야 하는 금액
				LL Money = (LL)floor(Must_Pay + 1e-12);
				if (Taxi.Money < Must_Pay) { // 현재 가진 돈이 지불해야 할 금액보다 부족하다면
					Taxi.Fuel += (LD)Taxi.Money / Price; // 남은 금액 / 주유소의 1갤런당 가격 = 금액을 모두 지불하고 받는 연료
					Taxi.Fuel = min(Taxi.Fuel, (LD)A);
					Taxi.Money = 0;
				}
				else { // 현재 가진 돈이 지불해야 할 금액 이상이라면 금액만큼 지불하고 연료를 가득 채운다.
					Taxi.Money -= Money;
					Taxi.Fuel = A;
				}
			}
		}
		else if (CMD.substr(0, 28) == "Pickup a passenger going to ") { // 문장의 앞이 Pickup으로 시작한다면
			string Dest = CMD.substr(28); // 목적지
			Passenger.push_back({ Dest,0 });
			if (Passenger.size() > 3) { // CAPACITY FULL : 정원보다 많은 승객을 태우려고 할 때
				cout << "CAPACITY FULL" << "\n";
				return 0;
			}
		}
	}
	if (Taxi_Pos != Taxi_Garage_Pos) { // NOT IN GARAGE : 마지막 지점이 Taxi Garage가 아닐 때
		cout << "NOT IN GARAGE" << "\n";
		return 0;
	}
	else {
		if (!Passenger.empty()) { // REMAINING PASSENGER : 마지막 지점이 Taxi Garage이지만 아직 내리지 못한 승객이 있을 때
			cout << "REMAINING PASSENGER" << "\n";
			return 0;
		}
		else { // 규칙에 맞게 운행을 완료한 경우, 최종적으로 번 돈의 액수를 출력한다.
			cout << Taxi.Money << "\n";
		}
	}

	return 0;
}

'BOJ > Platinum ~ Diamond' 카테고리의 다른 글

[BOJ/Platinum 4] 백준 15778 Yut Nori(C++) (0)	2022.02.04
[BOJ/Platinum 5] 백준 20541 앨범정리(C++) (0)	2022.02.02
[BOJ/Platinum 5] 백준 18891 제21대 국회의원 선거(C++) (0)	2022.01.31
[BOJ/Platinum 5] 백준 2505 두 번 뒤집기(C++) (0)	2022.01.30
[BOJ/Platinum 4] 백준 3111 검열(C++) (0)	2022.01.29

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`