[ boj : 2157 ] 여행

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

2157번: 여행

해설 : 전형적인 디비 문제이지만, 기저조건이 전 좀 까다로웠던 것 같습니다.....

 

n과 m 이 둘다 1일때만 시작과 종료가 가능하니 이걸로 기저조건을 주었고, 만약 둘중에 하나만 1이된다면 이 뜻은 1번도시부터 출발하지 않았다는 뜻과 1번 도시부터 출발하였지만 제한m을 충족시키지 못했다는 뜻이므로 return 해주었습니다.

 

또한, 이 조건들을 통과하고 나면 ret를 매우매우 작은값으로 변경시켜주었습니다. 그 이유는 return 해주고 기내식 점수를 더해야 되는데 0으로 변경해버리면 유효한 값이라고 착각하여 답을 재대로 도출 하지 못할 수도 있으니, 매우 작은값으로 초기화하여 무의미한 값으로 만들어버렸습니다.

 

이에 대한 더 좋은 방법이 있을지 전 잘 모르겠네요...아마 저가 탑-다운 방식으로 코드를 짜서 그런가,,,,,바텀-업 방식은 다를수도 있겠군요.

 

#include<bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;
int n, m, k;
int dp[310][310];
vector<pair<int,int>> v[310];

int f(int x, int y);

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	cin >> n >> m >> k;
	int x, y, z;
	for (int i = 0; i < k; i++) {
		cin >> x >> y >> z;
		v[y].push_back({ x,z });
	}
	memset(dp, -1, sizeof(dp));
	int ans = -1;
	for (int i = 1; i <= m; i++)
		ans = max(ans, f(n, i));
	cout << ans;
	return 0;
}
int f(int x, int y)
{
	if (x == 1 && y == 1)return dp[x][y] = 0;
	if (x <= 1 || y <= 1)return -INF;
	int& ret = dp[x][y];
	if (ret != -1)return ret;	

	ret = -INF;
	for (pair<int, int> u : v[x])
		if (x > u.first) 
			ret = max(ret, f(u.first, y - 1) + u.second);
		
	return ret;
}