[BOJ] 백준 2157. 여행 (Gold IV)

좀 신기하고도 인상깊었던 문제를 기억 속에 오래 남아두게 하기 위해 포스팅한다.

www.acmicpc.net/problem/2157

2157번: 여행

문제를 읽으면 그래프 이론이 먼저 생각나나, 

같은 간선이 여러 개 있을 수 있다는 점, 그리고 가장 최대의 값을 골라야 한다는 점이

dp를 떠올리게 했다.

만약, 같은 간선이 여러개 있지 않고 하나만 있는 상태로 최대를 뽑아내는 문제라면 오히려 다익스트라를 역방향으로 돌려서 진행하지 않았을까 싶다.

 

---

의식의 흐름 및 해설

사실 이 문제는 처음에 보기엔 쉽고 그냥 풀릴 만한 dp인줄 알았다.

그런데 생각해보니 반드시 M개 이하의 도시를 지나야 되고 반드시 N번 도시에서의 최대값을 구해야 하는 문제이다보니 여러가지 생각할 게 있는 문제이다.

사실 M개 이하의 도시를 지나야 한다는 조건은 단순히 if문으로 처리해주면 되는 문제라 크게 생각이 필요가 없다.

그래서 맨 처음엔 코드를 아래와 같이 짰었다.

 

(주의) 틀린 코드입니다.

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAX = 301;
const int INF = 1e9 + 7;
int N, M, K, d[MAX][MAX], ans;
vector<pair<int, int>> v[MAX];
int dp(int cur, int cnt) {
	int& ret = d[cur][cnt];
	if (ret != -1)
		return ret;
	if (cur == N - 1)
		return ret = 0;
	if (cnt >= M)
		return ret = -INF;
	ret = 0;
	for (auto i : v[cur]) {
		if (i.second > cur)
			ret = max(ret, dp(i.second, cnt + 1) + i.first);
	}
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M >> K;
	for (int i = 0; i < K; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		a--; b--;
		if (a < b)
			v[a].push_back({ cost, b });

	}
	memset(d, -1, sizeof(d));
	cout << dp(0, 1) << "\n";
}

그런데, 이 코드가 왜 틀릴까?

아래 테스트케이스를 보면서 얘기해보자.

3 3 2
1 2 3
1 3 1

ans: 1
wrong: 3

이 테스트케이스를 보면 느낀 점이 있겠지만,

도착점이 꼭 N이 아니어도, 단순히 더 큰 값이 나올 경우, 그 값으로 갱신해버린다.

따라서 우리는 ret=0; 으로 두면 안된다.

 

ret=-INF; 와 같은 아예 나올 수 없는 최솟값으로 둔 다음에,

도시가 N번에 도착하는 경우에만 0 이상의 현재 값으로 갱신해주고, 그 외의 경우는 -INF를 리턴해주게 해야 한다.

개인적으로 이러한 점을 몰라서 굉장히 고생했던 문제가 있는데, 바로 아래 문제이다.

www.acmicpc.net/problem/20925

20925번: 메이플스토리

(아아... 지금은 망해버린 그 게임)

이 문제 또한 지금 포스팅하는 문제와 조금 아이디어가 비슷하다.

다만, 이 문제보다 난이도가 높은 편이니 이 문제를 풀고 시도해볼 것을 추천한다.

---

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
const int MAX = 301;
const int INF = 1e9 + 7;
int N, M, K, d[MAX][MAX], ans;
vector<pair<int, int>> v[MAX];
int dp(int cur, int cnt) {
	int& ret = d[cur][cnt];
	if (ret != -1)
		return ret;
	if (cur == N - 1)
		return ret = 0;
	if (cnt >= M)
		return ret = -INF;
	ret = -INF;
	for (auto i : v[cur]) {
		if (i.second > cur)
			ret = max(ret, dp(i.second, cnt + 1) + i.first);
	}
	return ret;
}
int main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(false);

	cin >> N >> M >> K;
	for (int i = 0; i < K; i++) {
		int a, b, cost;
		cin >> a >> b >> cost;
		a--; b--;
		if (a < b)
			v[a].push_back({ cost, b });

	}
	memset(d, -1, sizeof(d));
	cout << dp(0, 1) << "\n";
}

역시 탑다운충 kth990303...

---

쉬운 dp일줄 알았는데 얻을 점이 많은 좋은 문제였다.

그리고 그래프 이론 문제처럼 보이는 dp문제라 더 신선하고 재밌는 문제인 듯하다.