[BOJ] 14863 : 서울에서 경산까지 -travelbeeee

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

---

[ 알고리즘풀이 ]

2차원 DP 배열을 이용하면 문제를 해결할 수 있습니다.

'DP[i][j] := 구간 i를 j분 안에 지났을 때 최대로 얻을 수 있는 금액' 으로 정의하면 됩니다.

i == 1인 첫 번째 구간에서만 초기값을 설정해주고, 그 뒤로는 들어온 입력 값에 따라 현재 j 분에서 도보 혹은 자전거로 이동할 수 있는 경우(시간이 K분을 안 넘는 경우) 만 DP 배열을 갱신해주면 됩니다.

#include<iostream>
#include<algorithm>
using namespace std;

int dp[101][100001] = {};

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);

	int N, K, a, b, c, d;
	cin >> N >> K;
	for (int i = 1; i <= N; i++){
		cin >> a >> b >> c >> d;
		if(i == 1){
			dp[i][a] = b;
			dp[i][c] = max(dp[i][c], d);
		}
		else {
			for (int j = 0; j <= K; j++) {
				if (dp[i - 1][j] == 0) continue; // 전에 도시도 안밟은경우.
				else {
					if (j + a <= K) //시간이넉넉
						dp[i][j + a] = max(dp[i][j + a], dp[i - 1][j] + b);
					if (j + c <= K)
						dp[i][j + c] = max(dp[i][j + c], dp[i - 1][j] + d);
				}
			}
		}
	}
	

	int m = -1;
	for (int i = 1; i <= K; i++)
		m = max(m, dp[N][i]);
	cout << m;
	return 0;
}

---