[종만북 문제] 달팽이 (문제 ID : SNAIL, 난이도 : 하)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 시시해서 죽고 싶어졌다.

[종만북 문제] 달팽이 (문제 ID : SNAIL, 난이도 : 하)

쉬운 DP 문제다. 점화식만 잘 세우면 되는데... 책에서는 아래처럼 만들더라.

 

나 같은 경우, 아래와 같이 풀었다. 점화식의 원리는 거의 동일하다!

#include <iostream>
#include "stdlib.h"
#include <cmath>
#include <vector>
#include <map>
#include <algorithm>
#include <unordered_map>

using namespace std;

/****************************************************************************************************/

int N; // 우물의 깊이
int M; // 장마 기간

const double RAIN = 0.75;
const int DAYS = 1001;

unordered_map<int, double> cache;

double calc(int days, int dist)
{
	// 기저 케이스 : 불가능
	if (days * 2 < dist)
		return 0.0;

	// 기저 케이스 : 불가능
	if (days == 0 && dist > 0)
		return 0.0;

	// 기저 케이스 : 가능
	if (days >= 0 && dist <= 0)
		return 1.0;

	if (cache.count(days * DAYS + dist))
		return cache[days * DAYS + dist];
	
	double ret = 0.0;
	ret = 0.75 * calc(days - 1, dist - 2) + 0.25 * calc(days - 1, dist - 1);
	cache[days * DAYS + dist] = ret;

	return ret;
}

void sol()
{
	cache.clear();
	//cout << calc(N, M) << endl;
	printf("%.10f\n", calc(M, N));
}

void inputHandler()
{
	cin >> N;
	cin >> M;
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		inputHandler();

		sol();
	}

	return 0;
}

 

😄