백준 2157번 여행

🔒 문제 url

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

🔑알고리즘

2차원 dp 배열을 선언한다. 의미는 다음과 같다.
dp[x][cnt] : $cnt$번 이동하여 $x$번 도시로 갈 때의 최댓값

$a$번 도시에서 $b$번 도시로 이동할 수 있고, 현재까지 $k$번 이동했다고 할 때, 비교할 값은 다음 두 가지이다.
1. $a$번 아닌 다른 도시에서 $b$번 도시까지 $k+1$번 이동하여 도착했을 때의 최댓값
= dp[b][k+1]
2. $a$번 도시에서 $b$로 이동할 때의 값 = dp[a][k] + (a에서 b로 가는기내식 점수)

• 즉, 점화식은 다음과 같다.

dp[next][cnt] = max(dp[next][cnt],dp[now][cnt-1]+dist);

$cnt$를 증가시키며, 1번 노드부터 시작하여 연결된 도시를 방문하며 dp 값을 갱신한다.
이후 dp[n][ ] 값 중 최댓값을 출력한다.

🐾부분 코드

void INPUT()
{
    IAMFAST
    cin >> n >> m >> k;
    for(int i = 0; i < k; i++)
    {
        int a,b,c; cin >> a >> b >> c;
        if(a < b) graph[a].emplace_back(b,c);
    }
}

<입력 함수>
도시 번호가 증가하는 방향으로만 이동하므로, $a < b$일 때에 한하여 항로를 연결한다.

//Init
memset(dp,-1,sizeof dp);
for(int i = 0; i < graph[1].size(); i++)
	dp[graph[1][i].first][2] =
		max(dp[graph[1][i].first][2],graph[1][i].second);

<dp 배열 초기화>
1번 도시에서 한 번만 이동하여 갈 수 있는 도시들에 대해 기내식 점수를 표기한다.

//DP
for(int cnt = 2; cnt < m; cnt++)
{
    for(int now = 1; now <= n; now++)
    {
        for(int j = 0; j < graph[now].size(); j++)
        {
            int next = graph[now][j].first;
            int dist = graph[now][j].second;
            if(dp[now][cnt] == -1) continue;

            dp[next][cnt+1] = max(dp[next][cnt+1],dp[now][cnt]+dist);
        }
    }
}

<dp 배열 갱신>
$cnt$번으로 도달할 수 없는 도시라면 탐색하지 않는다.
이외에는 위에서 설명한 알고리즘을 따라 갱신한다.

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

<출력>
$n$번 도시에 가는 경로 중 기내식 점수가 최대일 때의 값을 출력한다.

🪄전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
using namespace std;
#define IAMFAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);

int n,m,k;
typedef pair<int,int> pii;
vector<pii> graph[301];
int dp[301][301];

void INPUT()
{
    IAMFAST
    cin >> n >> m >> k;
    for(int i = 0; i < k; i++)
    {
        int a,b,c; cin >> a >> b >> c;
        if(a < b) graph[a].emplace_back(b,c);
    }
}

void SOLVE()
{
    //Init
    memset(dp,-1,sizeof dp);
    for(int i = 0; i < graph[1].size(); i++)
        dp[graph[1][i].first][2] =
                max(dp[graph[1][i].first][2],graph[1][i].second);

    //DP
    for(int cnt = 2; cnt < m; cnt++)
    {
        for(int now = 1; now <= n; now++)
        {
            for(int j = 0; j < graph[now].size(); j++)
            {
                int next = graph[now][j].first;
                int dist = graph[now][j].second;
                if(dp[now][cnt] == -1) continue;

                dp[next][cnt+1] = max(dp[next][cnt+1],dp[now][cnt]+dist);
            }
        }
    }

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

int main()
{
    INPUT();
    SOLVE();
}

🥇문제 후기

Dijkstra로 못 풀 이유가 없어보여 접근해봤지만.. 결국 실패하고 DP로 돌아섰다.
결국에는 Dijkstra로 풀 수 있었기에 미련이 남는 문제다..😟
그래도 오랜만에 백준 포스팅하니 기분은 좋다..!😤