알고스팟: 장마가 찾아왔다 (ID: SNAIL)

[문제 링크]

algospot.com :: SNAIL

---

알고리즘 문제해결전략 책에 나와있는 알고리즘과 동일하게 구현하였다.

 

제대로 구현한 것이 분명한데 자꾸 쌩뚱맞은 결과가 출력되어서 골머리를 앓았다.

double형 2차원 배열을 memset()함수를 통해 -1로 초기화했다는 것이 오답의 원인이었다.

이중 for문으로 memo[1001][2001] 배열을 -1로 초기화하여 문제를 해결하였다.

---

#include <cstdio>
using namespace std;

double memo[1001][2001];
int n, m;

double Solution(int days, int clime)
{
	if (days == m) return clime >= n ? 1 : 0;

	double& ret = memo[days][clime];
	if (ret != -1) return ret;

	return ret = (0.25 * Solution(days + 1, clime + 1)) + (0.75 * Solution(days + 1, clime + 2));
}
int main(void)
{
	int tc;
	scanf("%d", &tc);

	while (tc--)
	{
		for (int i = 0; i < 1001; i++)
			for (int j = 0; j < 2001; j++)
				memo[i][j] = -1;

		scanf("%d %d", &n, &m);
		printf("%.10f\n", Solution(0, 0));
	}

	return 0;
}

알고리즘 200일 프로젝트 - 55 day