서울에서 경산까지 14863

문제

접근 방법

단순하게 반복문+점화식으로 접근하려 했는데 안 됐다.
그래서 다른 사람의 풀이법을 보았다.
재귀함수를 이용하여서 풀면 됐다.

코드

#include <iostream>
#include <vector>
using namespace std;
struct node
{
    int time1, money1, time2, money2;
};
vector<node> v;
int N, K;
vector<vector<int>> dp;
int recur(int n, int k)
{
    if (k < 0)
        return -100000000;
    else if (n == N)
        return 0;
    if (dp[n][k])
        return dp[n][k];
    return dp[n][k] = max((recur(n + 1, k - v[n].time1) + v[n].money1), (recur(n + 1, k - v[n].time2) + v[n].money2));
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> N >> K;
    v = vector<node>(N);
    dp = vector<vector<int>>(N, vector<int>(K + 1));
    for (int i = 0; i < N; ++i)
        cin >> v[i].time1 >> v[i].money1 >> v[i].time2 >> v[i].money2;
    cout << recur(0, K);
    return 0;
}

풀이

반복문으로도 풀 수 있는 문제였다.
0번째 인덱스는 그냥 집어넣고 그 뒤에 인덱스에서는 이전 인덱스를 발판 삼아서 DP를 채우는 방식이었다.