백준[14863] - 서울에서 경산까지

문제

백준 14863 문제 보기

접근 방법

빠르게 틀을 만들어 놓고 이상한 곳에서 실수를 너무 많이했다. 문제 접근은 처음 도보와 자전거를 모두 dfs로 탐색한다. 하지만 이전에 진행했던 경로를 저장하지 않으면 시간복잡도는 O(2^n)으로 시간 초과를 유발한다. 따라서 이전에 지나갔던 노드라면 memo에서 꺼내어 여지껏 노드까지 온 거리를 더해서 리턴한다.
하지만 실수가 2가지 있었다. 목적지에 도착했을때만 memo에 값을 저장했다. 목적지 이동 도중 이미 제한된 시간을 넘어서 지나가면 안되는 길을 저장하지않아 제출했을때 시간 초과가 났다. 이를 해결하고 다시 제출했을때 또 문제가 있었다. 제한 시간과 소모 시간을 비교하는 if(time > k)가 memo보다 아래에 있어 memo[cnt][time]을 수행할때 index out of array로 틀렸었다.

코드

#include <iostream>
#include <cstring>

using namespace std;

#define IMPOSSIBLE (-987654321)

int N, K;
int arr[101][5];
int memo[101][100001];

int dfs(int cnt, int money ,int time) {
    if(time > K) {
        return IMPOSSIBLE;
    }

    if(memo[cnt][time] == IMPOSSIBLE) {
        return IMPOSSIBLE;
    }

    if(cnt == N && time <= K) {
        return money;
    }

    if(memo[cnt][time] != -1) {
        return memo[cnt][time] + money;
    }

    int val = IMPOSSIBLE;
    val = max(val, dfs(cnt + 1, money + arr[cnt + 1][2], time + arr[cnt + 1][1]));
    val = max(val, dfs(cnt + 1, money + arr[cnt + 1][4], time + arr[cnt + 1][3]));

    if(val == IMPOSSIBLE) {
        memo[cnt][time] = IMPOSSIBLE;
    } else {
        memo[cnt][time] = val - money;
    }

    return val;
}

int main() {

    cin >> N >> K;

    memset(memo, -1, sizeof(memo));

    // 시간, 모금액, 자전거 시간, 자전거 모금액
    for(int i = 1; i <= N; i ++) {
        cin >> arr[i][1] >> arr[i][2] >> arr[i][3] >> arr[i][4];
    }

    int ans = dfs(1, arr[1][2], arr[1][1]);
    ans = max(ans, dfs(1, arr[1][4], arr[1][3]));

    cout << ans << endl;

    return 0;
}