[백준/Baekjoon] 2175 여행 C++ :: Dynamic Programming

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

2157번: 여행

---

1. Logic

동일한 경로의 비행기 노선이 있을 수 있기 때문에 기내식의 점수가 가장 높은 것 만을 입력받아줬다.

그리고 DP배열이 의미하는 바는 당연 가장 높은 기내식 점수이다.

dp[도시의 번호][몇번째로 방문한 도시인지]

---

2. Code

#include<vector>
#include<cstring>
#include <iostream>
#include<algorithm>

using namespace std;

int n, m, k;
const int INF = 0x3f3f3f3f;

int dp[301][301];
int input[301][301];

int solve(int node, int cnt) {
    if(node != n && cnt == m) return -INF;
    if(node == n) return 0;
    
    int &ret = dp[node][cnt];
    
    if(ret != -1) return ret;
    
    ret = -INF;
    
    for(int i = node+1; i <= n; i++) {
        if(input[node][i]) {
            ret = max(ret, solve(i, cnt+1) + input[node][i]);
        }
    }
    
    return ret;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    memset(dp, -1, sizeof(dp));
    
    cin >> n >> m >> k;
    
    for(int i = 0; i < k; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        
        input[a][b] = max(input[a][b], c);
    }
    
    cout << solve(1, 1);
}

---

3. Feedback

처음에 문제를 보고 다익스트라 알고리즘으로 풀 수 있을 줄 알았다. 가지치기만 잘 하면 될것같은데 생각이 잘 안떠올랐다.

알고리즘 Solve 후 제가 생각한 Logic을 기록하는 개인 공부 블로그입니다.
내용 중 최적화가 가능한 부분등은 언제든지 댓글로 틀린 부분 및 피드백 주시면 공부 및 반영하겠습니다🧐