BOJ 14863 서울에서 경산까지

서울에서 경산까지

(http://boj.kr/14863)

냅색문제처럼 경로 둘 중 하나를 골라서 쌓는다는 느낌으로 구하면 된다.

나는 D[i][j] = i번째 경로까지 j분 이하의 시간으로 얻을 수 있는 최대 모금액

이라고 정하고 풀었다.

그러면 식은,

D[i][j] = max(D[i - 1][j - 도보로 걸리는 시간] + 도보로 모으는 모금액, D[i - 1][j - 자전거로 걸리는 시간] + 자전거로 모으는 모금액)이 된다.

하지만 이런 식으로 하면 i - 1번째 경로까지를 j - 시간만에 갈 수 있는지를 따로 확인해야한다.

#include <bits/stdc++.h>
 
using namespace std;
 
int tme[101][2], money[101][2], d[101][100001];
 
int main() {
    int n, k, ans = 0;
 
    scanf("%d %d", &n, &k);
 
    for (int i = 1;i <= n;++i)
        scanf("%d %d %d %d", &tme[i][0], &money[i][0], &tme[i][1], &money[i][1]);
 
    for (int i = 1;i <= k;++i)
        d[1][i] = max(tme[1][0] > i ? 0 : money[1][0], tme[1][1] > i ? 0 : money[1][1]);
    for (int i = 2;i <= n;++i)
        for (int j = 1;j <= k;++j) {
            if (j >= tme[i][0] && d[i - 1][j - tme[i][0]] != 0)
                d[i][j] = d[i - 1][j - tme[i][0]] + money[i][0];
            if (j >= tme[i][1] && d[i - 1][j - tme[i][1]] != 0)
                d[i][j] = max(d[i][j], d[i - 1][j - tme[i][1]] + money[i][1]);
        }
 
    printf("%d", d[n][k]);
 
    return 0;
}