[Algorithm]Baekjoon 14863번 :: 서울에서 경산까지

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
 
using namespace std;
 
 
struct Node
{
    int time;
    int money;
};
 
int n, k; 
int dp[101][100001] = { 0 };
Node infos[101][2];
 
const int minNum = -123456789;
 
int DFS(int curIndex, int curTime)
{
    int& result = dp[curIndex][curTime];
    if (result != -1) return result;
 
    if (curIndex == n) return 0;
    if (curTime == 0)
    {
        return minNum;
    }
 
    int first = minNum;
    int second = minNum;
 
    // 가능한 경우만 이동.
    if (curTime - infos[curIndex + 1][0].time >= 0) // 도보이동가능하면
    {
        first = DFS(curIndex + 1, curTime - infos[curIndex + 1][0].time) + infos[curIndex+1][0].money;
    }
 
    if (curTime - infos[curIndex + 1][1].time >= 0) // 바이크이동 가능하면
    {
        second = DFS(curIndex + 1, curTime - infos[curIndex + 1][1].time) + infos[curIndex+1][1].money;
    }
 
    return result = max(first, second);
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n >> k;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> infos[i][0].time >> infos[i][0].money >> infos[i][1].time >> infos[i][1].money;
    }
 
    memset(dp, -1, sizeof(dp));
    cout << DFS(0, k);
}
 
 

 

 

이 문제가 냅색문제랑 다른점은, 매번 선택지 2개마다 한개를 '반드시' 골라야 한다는 것이다.

그리고 무조건 끝 인덱스까지 도달해야 '유효한 경로'가 된다는 것이다.

 

풀이는 Top-Down으로 했으며, 방문여부 자체를 위해 dp테이블은 -1로 memset, 그리고 유효한 경로인지 아닌지 여부를 판별하기위해 minNum값을 따로 정의했다.

 

현재 남아있는 시간에 따라 도보나 자전거를 선택해서 탐색을 하며, 만약 탐색을 들어갔는데 끝인덱스일 경우, 즉 도착했으면 0을 리턴하고 종료.

 

끝인덱스가 아닌데 잔여시간이 없다? 그러면 이 경로자체가 유효하지 않다는것이기 때문에 유효하지않다는 표시를 해줘야 한다. 그 표시를 minNum으로 체크한다.

 

방문여부와 유효한 경로인지 아닌지를 잘 구별해야 한다.