[UVa][C++] 301: Transportation (수송)

문제 링크

• UVa: https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=237
• 백준: https://www.acmicpc.net/problem/7370

 

문제가 번역이 돼있지 않기 때문에 간략히 문제 설명을 써보겠습니다.

A역에서 B역까지 가는 승차정원이 n명인 열차가 있고, 기차표 예매 내역을 보고 어떻게 사람들을 골라 태워야 최대의 수익을 낼 수 있는지 구하는 문제입니다. 예매 내역은 1건당 출발지, 도착지, 인원수로 되어 있고, 한 예매내역을 취소시키든가, 전부 태우든가 해야합니다. 절반만 태우고 이렇게 하지 못합니다. 열차 요금은 이동거리 * 인원수 입니다.

 

예제 input의 첫 번째 test case입니다. 화살표에 적힌 숫자는 인원수고 밑에 적힌 숫자는 요금입니다.

이 경우 0->2, 1->2, 2->3 가는 손님들을 태울 때 요금의 합계가 19로 최대가 됩니다.

 

완전탐색으로 풀면 됩니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>

using namespace std;


int from[22], to[22], people[22];
int station[8];
int max_earning, sum, orders;


void dfs(int current) {
	//마지막 역인 경우
	if (current == orders) {
		max_earning = max(max_earning, sum);
		return;
	}

	bool possible = true;

	//이번 order 예약 가능한지 체크
	for (int i = from[current]; i < to[current]; ++i) {
		if (station[i] < people[current]) {
			possible = false;
			break;
		}
	}

	//이번 order 포함
	if (possible) {
		//거치는 모든 역 좌석 수 감소
		for (int i = from[current]; i < to[current]; ++i)
			station[i] -= people[current];
		sum += people[current] * (to[current] - from[current]);
		
		dfs(current + 1);

		for (int i = from[current]; i < to[current]; ++i)
			station[i] += people[current];
		sum -= people[current] * (to[current] - from[current]);
	}

	dfs(current + 1);
}

int main()
{
#ifndef ONLINE_JUDGE
	freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	
	int capacity, num_of_station;
	while (cin >> capacity >> num_of_station >> orders) {
		if (!capacity && !num_of_station && !orders) break;

		for (int i = 0; i < orders; ++i)
			cin >> from[i] >> to[i] >> people[i];

		for (int i=0; i<num_of_station; ++i)
			station[i] = capacity;

		max_earning = 0;
		sum = 0;

		dfs(0);

		cout << max_earning << '\n';
	}
	
	return 0;
}