22358 스키장

으아악.. dp인데 상태 저장해야 하는 문제들 너무 어렵다;; 낯설어;;  친해지기도 힘듬;;

 

이전에 풀었던 https://burningjeong.tistory.com/388 관악산 문제 + 벽 부수기랑 비슷한 느낌이다. 

 

전체 코드는 아래랑 같은데 일단 다시 정리 겸 조각조각 땃땃따 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <deque>
#include <stack>
#include <set>
#include <map>
#include <cmath>
#include <cstring>
#include <bitset>
#include <stdio.h>

#define xx first
#define yy second
#define all(x) (x).begin(), (x).end()

using namespace std;
using i64 = long long int;
using ii = pair<int, int>;
using iis = pair<int, string>;
using ii64 = pair<i64, i64>;
using iii = tuple<int, int, int>;

i64 n, m, k, s, t;

vector<i64> adj[100005];
i64         dp[100005][15]; // 출발 했을 떄의 시간의 최댓값
map<ii64, i64> height;

i64 dfs(i64 curr, i64 k) {
    if (dp[curr][k] != -1)
        return dp[curr][k];
    
    auto& res = dp[curr][k];
    res = -2;
    
    if (curr == t && k == 0)
        return res = 0;
    
    for (int i = 0; i < adj[curr].size(); i++) {
        if (curr < adj[curr][i]) {
            i64 next = dfs(adj[curr][i], k);
            if (next == -2)
                continue;
            res = max(res, next + height[{curr, adj[curr][i]}]);
        }
        else if (k > 0) {
            res = max(res, dfs(adj[curr][i], k - 1));
        }
    }
    
    return res;
}

int main() {
    scanf("%lld %lld %lld %lld %lld", &n, &m, &k, &s, &t);
    
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < m; i++) {
        i64 x, y, h;
        scanf("%lld %lld %lld", &x, &y, &h);
        
        adj[x].push_back(y);
        adj[y].push_back(x);
        height[{x, y}] = h;
        height[{y, x}] = h;
    }
    
    i64 res = dfs(s, k);
    
    if (res == -2)
        printf("-1");
    else
        printf("%lld", res);
    
    return 0;
}

 

----

분석

 

i64 n, m, k, s, t;

vector<i64> adj[100005];
i64         dp[100005][15]; // 출발 했을 떄의 시간의 최댓값
map<ii64, i64> height;

int main() {
    scanf("%lld %lld %lld %lld %lld", &n, &m, &k, &s, &t);
    
    memset(dp, -1, sizeof(dp));
    for (int i = 0; i < m; i++) {
        i64 x, y, h;
        scanf("%lld %lld %lld", &x, &y, &h);
        
        adj[x].push_back(y);
        adj[y].push_back(x);
        height[{x, y}] = h;
        height[{y, x}] = h;
    }
    
    i64 res = dfs(s, k);
    
    if (res == -2)
        printf("-1");
    else
        printf("%lld", res);
    
    return 0;
}

 

실수로 int로 했다가 틀려서 다 i64로 바꿔서 풀었다. 

기본값으로 dp에 -1로 초기화해줬다. 그리고 인접한 노드 연결하고 간선마다 시간도 저장했다. 

 

그 다음 시작지점에서 dfs 돌린다. 결과로 -2가 나오면 없는 경우이고 나머지면 출력하게 구현했다. 

 

i64 dfs(i64 curr, i64 k) {
    if (dp[curr][k] != -1)
        return dp[curr][k];
    
    auto& res = dp[curr][k];
    res = -2;
    
    if (curr == t && k == 0)
        return res = 0;

이미 값이 계산된 경우 dp에 있는 값을 반환한다. 

 

그게 아니라면 dp에 값을 집어넣어야 하는데 res를 맨 처음 -2로 초기화한다.

 

그 다음 현 위치가 종료 지점이고 k도 0이라면 움직일 수 없으므로 그냥 0을 반환한다. 

종료지점이지만 k가 0이 아니라면 움직일 가능성이 있으므로 다음 단계를 밟는다.

 

    for (int i = 0; i < adj[curr].size(); i++) {
        if (curr < adj[curr][i]) {
            i64 next = dfs(adj[curr][i], k);
            if (next == -2)
                continue;
            res = max(res, next + height[{curr, adj[curr][i]}]);
        }
        else if (k > 0) {
            res = max(res, dfs(adj[curr][i], k - 1));
        }
    }
    
    return res;

그 다음 연결된 노드를 확인한다. 

 

내려가는 노드라면 다음 노드를 기준으로 계산한다.

만약 -2라면 패스하고 그게 아니라면 다음 노드 기준으로 최대 시간 + 다음 노드로 가는 시간을 계산한다. 

 

올라가는 노드라면 k-1을 한 값을 계산하면 된다. 끝~ 어렵다