백준, boj) 2157. 여행 (C / C++)

1. 문제 링크

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

2157번: 여행

2. 문제 개요

M개 이하의 도시를 지나는 여행을 계획하려 한다. 여행경로는 반드시 1번 도시에서 시작해서 N번 도시에서 끝나야 한다.

한 번 서쪽으로 이동했다가 다시 동쪽으로 이동할 수 없다. 그래서 계속 서쪽으로만 (숫자가 증가하는 방향으로 만) 이동해야 한다.

 

이동하면서 최대한 맛있는 기내식만 먹으면서 이동하려 한다.

 

항로 개설 여부와 해당 항로에서 제공되는 기내식의 점수가 주어졌을 때 먹게 되는 기내식의 점수의 총합이 최대가 되도록 하시오.

 

3. 문제 힌트

 

점화식을 구해보자.

총 합이 최대가 되도록, 즉 단계별로 최댓값을 갖고 가면 된다.

 

dp[n][m]으로 두자. n은 n번째 도시, m은 이때까지 이동한 마을의 개수이다.

 

dp[다음 도시][m]는 dp[이전도시][m-1]이 될 것이다. 이점 참고하여 풀어보자. 

 

 

4. 문제 풀이

 

(3) 번에 적었듯이 dp[n][m]으로 두어서 풀어야 한다.

 

우선 인접 리스트를 만들어야 한다. 역순으로 가는 경우는 인접 리스트에 넣어주지 말자.

 

인접 리스트를 만들고,

bottom up으로 진행할 것이기 때문에 dp table의 기저 부분을 채워주자.

 

1과 연결된 모든 정점 next에 대하여

 dp[next][2] = max(dp[next][2], dp[cur][1]+ weight)이고, 여기서 dp [cur][1]는 0이다.

 

그러면,

dp[도시][2]에는 1에서 출발해 2번만에 도달할 수 있는 도시의 최대점수가 주어진다.

 

여기서 도시는 1~n이다.

따라서, dp[도시][2] 중에서 0이 아닌, 즉 갱신된(도달한) 마을에 대해서 1에서 했던 것처럼 또 뻗어 나가 준다.

dp[next][m+1] = max(dp[next][m+1] , dp[cur][m]+weight);가 될 것이다. weight는 cur -> next로 갈 때의점수. ( 여기서 m은 1~m이다.)

 

이것을 m번 이동했을 때까지 계산하고

 

최댓값은 dp[n][2] ~ dp[n][m]중 1개이다.

 

5. 코드

#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;

int n, m, k, ans;
vector <vector<pair<int, int>>> adj;	//dest, weight
int dp[301][301];

int main()
{
	scanf("%d %d %d", &n, &m, &k);
	adj.resize(n + 1);

	for (int i = 0; i < k; ++i){
		int src, dest, weight;
		scanf("%d %d %d", &src, &dest, &weight);
		if (src > dest)	continue;
		adj[src].push_back({ dest,weight });
	}

	//init val;
	for (int i = 0; i < adj[1].size(); ++i){
		int next = adj[1][i].first;
		int weight = adj[1][i].second;

		dp[next][2] = max(dp[next][2],weight);
	}

	for (int i = 2; i <= m; ++i) {
		for (int cur = 1; cur <= n; ++cur){
			if (dp[cur][i] != 0){
				for (int j = 0; j < adj[cur].size(); ++j) {
					int next = adj[cur][j].first;
					int weight = adj[cur][j].second;

					dp[next][i + 1] = max(dp[next][i + 1], dp[cur][i] + weight);
				}
			}
		}
	}




	for (int i = 2; i <= m; ++i)
		ans = max(ans, dp[n][i]);

	printf("%d", ans);
	return 0;
}

6. 결과 사진

 

지적, 댓글 언제나 환영입니다~