문제 풀이

문제를 풀면서 좌절감을 크게 느꼈던 문제. 오랫동안 알고리즘 문제를 풀어오면서 실력이 늘지않았다는것을 다시한번 느끼게 됐다. 바텀업 방식을 버리고 탑다운 방식으로 연습을 해보기로 했다.

dp배열은 이차원 배열로 dp[i][j] 일때 i까지 j번을 걸쳐서 갔을 경우 최대 기내식 점수합으로 한다.

idx가 1이 아닌데 cnt가 1이라면 제한된 횟수안에 n 도시에 도착을 못한것이므로 -INF를 리턴한다.

그리고 n에 무사히 도착했을 경우에는 0을 반환한다.

dp[idx][cnt]는 동쪽으로만 이동하므로 1부터 idx - 1까지의 도시에만 들를 수 있고 그 항로가 존재해야 한다.
=> for(int i= 1; i< idx; i++)
=> if(arr[i][idx])

dp[idx][cnt] = max(dp[idx][cnt], solution(i, cnt - 1) + arr[i][idx])로,
idx에 최대 cnt번 걸쳐서 갈 경우 기내식의 최대 점수합은 i도시까지 cnt - 1번을 걸쳐서 갔을 경우 최대 기내식의 점수합 + i도시에서 idx도시로 갔을때 기내식 점수이다.

문제 링크

boj/2157

소스코드

PS/2157.cpp

#include <iostream>
#include <string>
#include <vector>
#include <map>
#include<algorithm>
#include<memory.h>
using namespace std;

int arr[301][301];
int dp[301][301];

int n, m, k;
int solution(int idx, int cnt);
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> m >> k;
	for (int i = 0; i < k; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (arr[a][b] <= c)
			arr[a][b] = c;
	}
	int ans = 0;
	memset(dp, -1, sizeof(dp));

	ans = solution(n, m);
	cout << ans;

}
int solution(int idx, int cnt)
{
	if (idx != 1 && cnt == 1)
	{
		return -987654321;
	}
	if (idx == 1)
	{
		return 0;
	}
	if (dp[idx][cnt] != -1)
		return  dp[idx][cnt];
	dp[idx][cnt] = -987654321;
	for (int i = 1; i < idx; i++)
	{
		if (arr[i][idx])
			dp[idx][cnt] = max(dp[idx][cnt], solution(i, cnt - 1) + arr[i][idx]);
	}
	return dp[idx][cnt];
}