동적 계획법 - 10. 우물을 기어오르는 달팽이

문제 : 달팽이 (난이도 : 下)

 

https://www.algospot.com/judge/problem/read/SNAIL

 

 분석

처음 풀면 매우 당황스러운 문제이다. 경우의 수를 구하는 것과 달리 확률은 어떻게 처리할지 고민이 된다.

그러나 코드를 한번 보고 나면 어떻게 처리할지 감이 잡힐 것이다.

 

※ 주의할 점이 하나 있는데 double형 배열을 memset으로 초기화하면 에러가 발생한다.

평소 하던 대로 하면 콘솔 창에 결괏값이 -nan이 나온다. 찾아보니 부동소수점 표기때문에 에러가 나는 것 같다.

필자는 간단하게 memset 대신 이중 for문으로 배열을 초기화했다.

 

 구현

#define MAX_N 1000

int n, m;
double cache[MAX_N][2 * MAX_N + 1];
//days동안 climbed[m] 올라왔을 때
//m일 전까지 n[m] 올라갈 확률
double climb(int days, int climbed)
{
	//base case : m일이 지난 경우
	if (days == m) return climbed >= n ? 1 : 0;
	//memoization
	double& ret = cache[days][climbed];
	if (ret != -1) return ret;
	return ret = 0.25*climb(days + 1, climbed + 1) + 0.75*climb(days + 1, climbed + 2);
}

int main()
{
	int c;
	cin >> c;
	while (c--)
	{
		//memset(cache, -1, sizeof(cache)); 
		//double 형에선 작동이 안된다. (nan:Not A Number)을 출력한다.
		//간단히 이중 for문으로 처리해준다.
		for (int i = 0; i < MAX_N; i++)
		{
			for (int j = 0; j < 2 * MAX_N +1; j++)
			{
				cache[i][j] = -1;
			}
		}
		cin >> n >> m;
		printf("%.10lf\n", climb(0, 0));
	}
	return 0;
}