백준 2157번 여행

개요

기존에 AC를 받아서 블로그 포스팅까지 완료했던 문제였는데 재채점 결과 WA를 받은 문제입니다.

(jaimemin.tistory.com/686)

 

 

기존의 문제점

DP를 구현할 때 초기 result 값을 결과값이 될 수 없는 값으로 초기화해야했는데, 결과값이 될 수 있는 0으로 초기화해서 WA를 받았습니다.

틀린 이유와 함께 반례도 제시해주신 xkdlaldfjtnl 님께 감사의 말씀을 드립니다.

 

전체적인 문제풀이를 참고하시고 싶으시다면 다음 링크를 참고해주세요.

 

변경된 코드

	#include <iostream>
	#include <algorithm>
	#include <cstring> //memset
	using namespace std;
	const int MAX = 300 + 1;
	const int INF = 987654321;
	int N, M, K;
	int dist[MAX][MAX];
	int cache[MAX][MAX]; //해당 도시, 몇번 방문?
	int maxTaste(int idx, int visit)
	{
	//기저 사례
	if (visit == M && idx != N)
	{
	return -INF;
	}
	//조건 성립
	if (idx == N)
	{
	return 0;
	}
	int &result = cache[idx][visit];
	if (result != -1)
	{
	return result;
	}
	result = -INF;
	//갈 수 있는 곳이면
	for (int to = idx + 1; to <= N; to++)
	{
	if (dist[idx][to])
	{
	result = max(result, dist[idx][to] + maxTaste(to, visit + 1));
	}
	}
	return result;
	}
	int main(void)
	{
	cin >> N >> M >> K;
	for (int i = 0; i < K; i++)
	{
	int city1, city2, taste;
	cin >> city1 >> city2 >> taste;
	//city1 -> city2 제일 맛있는 기내식을 채택
	dist[city1][city2] = max(dist[city1][city2], taste);
	}
	memset(cache, -1, sizeof(cache));
	cout << maxTaste(1, 1) << endl;
	return 0;
	}

view raw c++ hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~