[BOJ/백준][Gold4] 2157 : 여행 (C++)

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

2157번: 여행

 

 

[난이도] Gold4
[유형] DP

[풀이]

DP[n][m] : 현재 n 도시에 있고 m개의 도시를 지났을 때 얻을 수 있는 최대 점수

점화식
DP[n][m] max(adj[n][i]+sol(i,m+1)) : i는 n < i 이면서 n에서 i로 가는 경로 존재,
아무 도시도 갈 수 있다면 절대 나올 수 없는 값 -inf를 return하여 정답에서 제외.

 

 

#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
int N,M,K,adj[301][301],dp[301][301];
int sol(int n,int m){
    if(n==N) return 0;
    if(m==M) return -9e8;
    int& ret = dp[n][m];
    if(ret!=-1) return ret;
    ret = -9e8;
    for(int i=1;i<=N;i++) if(adj[n][i]) ret = max(ret,adj[n][i]+sol(i,m+1)); 
    return ret;
}
int main(){
    scanf("%d%d%d",&N,&M,&K);
    while(K--){
        int u,v,c;
        scanf("%d%d%d",&u,&v,&c);
        if(u<v) adj[u][v] = max(adj[u][v],c);
    }
    memset(dp,-1,sizeof(dp));
    printf("%d",sol(1,1) > 0 ? sol(1,1):0);
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/2157.cpp