여행(DP)

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

2157번: 여행

 

엣지들의 합이 최대가 되는 경로탐색 문제에서 M번이라는 횟수 제한이 추가되었다.

 

M번의 탐색이라는 제한이 걸려있으므로 이러한 정보를 저장하여야 한다.

 

그러므로 i번째 순서에 j라는 버텍스로 갔을때 엣지합의 최대값을 저장하여 DP를 활용한다.

DP[i][j] = i번째에 j에 도달했을때 엣지들의 최대 합

 

그래프를 1번부터 탐색하여 DP를 채워나간다

 

만약 2번에서 3번까지의 경로를 발견했다면

• 1번째에 3에 도달했을 때의 합 = max(기존 값, 0번째에 2에 도달했을 때의 합 + 2~3의 값)
• 2번째에 3에 도달했을 때의 합 = max(기존 값, 1번째에 2에 도달했을 때의 합 + 2~3의 값)
• ...
• M번째에 3에 도달했을 때의 합 = max(기존 값, M-1번째에 2에 도달했을 때의 합 + 2~3의 값)

 

이와 같이 DP 배열을 채워나가면 된다.

이 때, M-1번째에 2에 도달했어야만, 즉 값이 세팅되어있어야만 계산을 해야함에 유의하여야 한다.

이를 위해서 DP를 전부 -1로 초기화 해놓고 DP[0][1]을 0으로 세팅하고 진행하면 된다.

(0번째, 즉 시작할때 1에 있다는 의미)

DP[count][j] = max(DP[count][j], DP[count-1][i] + Edge[i][j]) ※DP[count-1][i] != -1

마지막에 DP[i][도착지점](1 <= i <= M)을 전부 탐색하여 가장 큰 값을 출력하면 된다.

 

#include <iostream>
#include <cstring>
using namespace std;

int Graph[301][301] = { 0, };
int DP[301][301] = { 0, };
// DP[i][j] -> i번째에 j로 갔을때 총 스코어
int N, M;

void Search()
{
	for (int i = 1; i <= N; i++)
	{
		for (int j = i + 1; j <= N; j++)
		{
			if (Graph[i][j] != 0)
			{
				for (int count = 1; count <= M; count++)
				{
					if (DP[count - 1][i] != -1)
					{
						DP[count][j] = max(DP[count][j], DP[count - 1][i] + Graph[i][j]);
					}
				}
			}
		}
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	M--;

	int cmd;
	cin >> cmd;
	while (cmd--)
	{
		int i, j, k;
		cin >> i >> j >> k;
		Graph[i][j] = max(Graph[i][j], k);
	}

	memset(DP, -1, sizeof(DP));
	DP[0][1] = 0;
	Search();
	int ret = 0;
	for (int i = 1; i <= M; i++)
	{
		ret = max(ret, DP[i][N]);
	}
	cout << ret;
}