[알고스팟][C++] SNAIL: 달팽이

문제 링크: https://algospot.com/judge/problem/read/SNAIL

 

종만북 동적계획법 파트에 있는 문제(258p)입니다. 근데 책에 오류가 있네요. 책은 10쇄입니다.

 

\begin{align} climb2(days,climbed) &= 0.25 \times climb2(days+1,climbed+1) \\ &+0.75 \times climb2(days+1,climbed+2)\end{align}

점화식이 이렇게 바뀌어야 됩니다. 앞에 예제랑 문제랑 조건이 뒤바꼈네요.

 

앞 예제 '우물을 기어오르는 달팽이'에서는 달팽이가 날이 맑을 때 2m를 올라가고, 비가 내리면 1m를 올라갑니다. 하지만 뒤의 예제 '장마가 찾아왔다'(ID: SNAIL)에서는 날이 맑으면 1m를 올라가고, 비가 내리면 2m를 올라갑니다.

 

틀린게 없는데 왜 자꾸 결과가 다르게 나오는지(맞왜틀?) 생각하다가 책에 틀린 부분이 있는 걸 발견했습니다.

 

#define _CRT_SECURE_NO_WARNINGS

#include <bits/stdc++.h>

using namespace std;


const int MAX_N = 1000;

int n, m;
double cache[MAX_N][2 * MAX_N + 1];

//달팽이가 days일동안 climbed 미터를 올라왔다고 했을 때
//m일 전까지 n미터를 기어올라갈 수 있는 확률
//1m 올라갈 확률 75%, 2m 올라갈 확률 25%
double climb2(int days, int climbed) {
	//base: m일이 모두 지난 경우
	if (days == m) return (climbed>=n?1:0);

	double& ret = cache[days][climbed];
	if (ret != -1.0) return ret;
	return ret = 0.25 * climb2(days + 1, climbed + 1) + 0.75 * climb2(days + 1, climbed + 2);
}

int main() {
#ifndef ONLINE_JUDGE
	//freopen("input.txt", "r", stdin);
#endif

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	int c;
	cin >> c;
	while (c--) {
		for (auto& r : cache)
			for (auto& c : r)
				c = -1.0;

		cin >> n >> m;
		cout.precision(10);
		cout << fixed << climb2(0, 0) << '\n';
	}


	return 0;
}

코드 작성하실 때 유의할 점은

• climb2 반환값은 경우의 수가 아니고 확률인 점
• cache는 double이기 때문에 memset 사용하면 안된다는 점

이 정도가 있는 것 같습니다.