BOJ 14863 - 서울에서 경산까지 ( KOI 초등, knapsack )

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

 

딱봐도 냅색이라 바로 풀었는데..

int f(int k, int t) {
	if (k == N) return 0; //계산의 통일성을 위해서 f(n,양수) = 0 이라고 함.

	int& ret = dp[k][t];
	if (ret != -1) return ret;

	ret = IMP;
	int time1 = opt[k].first.first, money1 = opt[k].first.second;
	int time2 = opt[k].second.first, money2 = opt[k].second.second;
	if (time1 <= t) ret = max(ret, money1 + f(k + 1, t - time1));
	if (time2 <= t) ret = max(ret, money2 + f(k + 1, t - time2));
	return ret;
}

 

기저, 메모이제이션 체크 후 ret의 디폴트값을 -1e9로 주지 않고, 0~-1000을 주면 틀렸습니다가 뜬다.

 

왜그럴까?

 

->IMP를 0으로 준다면, 그 이전까지 채운 모금액만큼은 모을 수 있다고 판단하는 것과 같다. 하지만 이는 틀린 말이고 아예 불가능한 경우이기 때문에 그 이전까지 채운 모금액도 마찬가지로 불능값이 돼야 한다. 따라서 IMP를 넉넉하게 -1e9로 줘야 한다.

 

f(k,t) = 남은 시간이 t이고 k번째 이후의 마을을 방문할때, 얻을 수 있는 모금액의 최대