[BOJ 13907 // C++] 세금

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 13907번 문제인 세금이다.
문제는 아래 링크를 확인하자.

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

13907번: 세금

도시 S에서 n까지 도로를 k개 이하개 거쳐갈 때의 최단거리를 저장하는 dp테이블 dp[k][n]을 생각하자. 이 dp테이블은 벨만-포드(Bellman-Ford) 알고리즘과 유사한 방식으로 진행해나가면 시간복잡도 O(NM)에 채울 수 있다.

 

세금이 총 P만큼 증가했을 때의 최소 비용은 min(dp[k][K] + P*k)가 된다. 이를 이용해 문제를 해결하자.

k는 N 이하(최단경로는 N개 이상의 노드를 경유하지 않는 점을 관찰하자)이므로, 모든 가능한 dp[k][K]값을 살펴보다도 시간복잡도 O(NK)로 문제를 해결하기에 충분한 시간복잡도임을 알 수 있다.

 

아래의 제출 코드는 min(dp[k][K] + P*k)를 찾는 과정을 CHT(Convex Hull Trick)을 이용해 이 과정의 시간복잡도를 O(N+K)로 한번 더 낮춘 코드이다. CHT를 모른다면 참고만 하고 넘어가자.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;

int N, M, K;
int S, D;

vector<pair<int, int>> G[1001];
int dist[1001][1001];

vector<pair<int, int>> stk;

void solve() {
	dist[0][S] = 1;
	for (int k = 0; k < N; k++) {
		for (int i = 1; i <= N; i++) {
			if (dist[k][i]) {
				if (dist[k + 1][i]) dist[k + 1][i] = min(dist[k + 1][i], dist[k][i]);
				else dist[k + 1][i] = dist[k][i];

				for (auto& nxt : G[i]) {
					if (dist[k + 1][nxt.first]) dist[k + 1][nxt.first] = min(dist[k + 1][nxt.first], dist[k][i] + nxt.second);
					else dist[k + 1][nxt.first] = dist[k][i] + nxt.second;
				}
			}
		}
	}
	
	stk.emplace_back(make_pair(0, 1000000007));
	for (int k = 1; k <= N; k++) {
		if (dist[k][D] == 0 || dist[k][D] == stk.back().second) continue;
		while (stk.size() > 1) {
			int idx1 = stk.size() - 1, idx2 = stk.size() - 2;
			ll a1 = stk[idx2].first, b1 = stk[idx2].second, a2 = stk[idx1].first, b2 = stk[idx1].second, a3 = k, b3 = dist[k][D];
			if (a1 * b3 + a2 * b1 + a3 * b2 >= a1 * b2 + a2 * b3 + a3 * b1) stk.pop_back();
			else break;
		}
		stk.emplace_back(make_pair(k, dist[k][D]));
	}
}


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> N >> M >> K >> S >> D;
	while (M--) {
		int x, y, w; cin >> x >> y >> w;
		G[x].emplace_back(make_pair(y, w));
		G[y].emplace_back(make_pair(x, w));
	}

	solve();

	cout << stk.back().second - 1 << '\n';

	int p = 0;
	while (K--) {
		int x; cin >> x;
		p += x;
		
		int idx1 = stk.size() - 1, idx2 = stk.size() - 2;
		while (stk[idx1].first * p + stk[idx1].second > stk[idx2].first * p + stk[idx2].second) {
			idx1--, idx2--, stk.pop_back();
		}

		cout << stk.back().first * p + stk.back().second - 1 << '\n';
	}
}