[백준 22358] 스키장

문제 링크 => 22358번: 스키장 (acmicpc.net)

22358번: 스키장

---

다이나믹 프로그래밍 문제이다.

 

문제의 조건에서 항상 ai < bi 로 주어지는 것으로 알 수 있는점 => DAG 이다.

 

리프트를 타지 않는 경우(K = 0) 와 리프트를 한번 이상 타는 경우(K >= 1) 로 나눠서 해결할 수 있다.

 

2차원 배열 dp[x][y] 를 시작지점 S에서 x까지 y번 리프트를 탔을때 시간이라고 한다.

 

접근 순서는 다음과 같다.

 

1. dp[1~N][0~K] = -1, dp[S][0] = 0 으로 초기화한다. ( -1 을 미리 채우는 이유는 이동할 수 없는 경우를 미리 채워두기 위함 )

 

2. 리프트를 타지 않는 경우에 대하여 dp 값을 먼저 채워주도록 한다.

for (int u = 1; u <= N; u++) {
	if (dp[u][0] == -1) continue;
	for (pair<int, int> p : go[u]) {
		int v = p.first;
		ll dist = p.second;
		dp[v][0] = max(dp[v][0], dp[u][0] + dist);
	}
}

(여기서 go 는 스키를 타고 내려올 수 있는 경로에 대한 벡터)

 

3. K = 0인 경우에 바로 dp[T][K] 값을 출력하고 K >= 1인 경우에 리프트를 타고 올라가고 다시 1부터 N 까지 스키를 타고 내려오는 시간을 1에서 K 만큼 업데이트 해준다.

for (int i = 1; i <= K; i++) {
	for (int u = N; u >= 1; u--) {
		for (pair<int, int> p : back[u]) {
			int v = p.first;
			ll dist = p.second;
			dp[v][i] = max(dp[v][i], dp[u][i - 1]);
		}
	}
	for (int u = 1; u <= N; u++) {
		if (dp[u][i] == -1) continue;
		for (pair<int, int> p : go[u]) {
			int v = p.first;
			ll dist = p.second;
			dp[v][i] = max(dp[v][i], dp[u][i] + dist);
		}
	}
}

(여기서 back은 리프트를 타고 갈 수 있는 경로에 대한 벡터)

 

리프트를 타고 올라가는 과정에서 역으로 N에서 1만큼 채워지는 부분을 살펴보도록 한다.

 

dp[v][i] = max(dp[v][i], dp[u][i - 1]);  (u는 현재 지점, v는 u에서 리프트를 타고 올라간 지점)

 

처음에 모든 dp값을 -1으로 초기화 하였으므로 dp[u][i - 1] 의 값 즉, i - 1 번 만큼 리프트를 타고 u에 도착했던 시간이 -1 이 아닌 경우는 결국 0 이상으로 dp[v][i] 에 채워지게 된다.

 

따라서 이러한 경우에 다시 스키를 타고 내려올때 v -> u 으로 이동하는 경우에 dp[u][i] = dp[v][i] + (v에서 u로 이동하는 시간) 으로 채워지게 된다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <stack>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M, K, S, T;
vector<pair<int, ll>> go[100001], back[100001];
ll dp[100001][11];

void input() {
	cin >> N >> M >> K >> S >> T;
	for (int i = 0; i < M; i++) {
		int a, b;
		ll t;
		cin >> a >> b >> t;
		go[a].push_back({ b,t });
		back[b].push_back({ a,t });
	}
}

void solve() {

	for (int i = 1; i <= N; i++) {
		for (int j = 0; j <= 10; j++) {
			dp[i][j] = -1;
		}
	}

	dp[S][0] = 0;

	for (int u = 1; u <= N; u++) {
		if (dp[u][0] == -1) continue;
		for (pair<int, int> p : go[u]) {
			int v = p.first;
			ll dist = p.second;
			dp[v][0] = max(dp[v][0], dp[u][0] + dist);
		}
	}

	for (int i = 1; i <= K; i++) {
		for (int u = N; u >= 1; u--) {
			for (pair<int, int> p : back[u]) {
				int v = p.first;
				ll dist = p.second;
				dp[v][i] = max(dp[v][i], dp[u][i - 1]);
			}
		}
		for (int u = 1; u <= N; u++) {
			if (dp[u][i] == -1) continue;
			for (pair<int, int> p : go[u]) {
				int v = p.first;
				ll dist = p.second;
				dp[v][i] = max(dp[v][i], dp[u][i] + dist);
			}
		}
	}

	cout << dp[T][K];
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	input();
	solve();

	return 0;
}