이번엔 DP

1. 시간과 돈을 입력받는다
2. 시간이 음수가 된 경우 이상한 값 return;
3. 만약 메모된 곳에 있으면 return;
4. 메모안되있으면, 리턴하면서 메모하기
   이 조건들은 기본적인 DP알고리즘이다, 4번에 저장할 값을 알아볼건데, 4번에 저장할 값은 크면서, 조건에 맞는 값이어야 된다. 일단 K를 기본 값으로 잡으면서 걸어가는 시간과, 자전거 타는 시간을 기준으로잡으면서 재귀를 돌리면 된다.

소스 코드

#include<iostream>
#include<string>
#include <algorithm>
#include<cmath>
#include<vector>

using namespace std;

#define INF 987654321;

int N, K;
struct dot {
	int m[2], w[2];
};
dot d[104];
int dp[104][100004];

int go(int min, int idx) {
	if (min < 0) return -INF;
	if (idx == N) {
		return 0;
	}
	if (dp[idx][min]) return dp[idx][min];

	return dp[idx][min] = max(
		go(min - d[idx].m[1], idx + 1) + d[idx].w[1],
		go(min - d[idx].m[0], idx + 1) + d[idx].w[0]);
}

int main() {
	cin >> N >> K;
	for (int i = 0; i < N; i++) {
		cin >> d[i].m[0] >> d[i].w[0] >> d[i].m[1] >> d[i].w[1];
	}
	cout << go(K, 0);
}