SNAIL(달팽이)

(출처) https://algospot.com/judge/problem/read/SNAIL

한번의 상황에서 생기는 2가지의 경우를 합치기

DP문제를 풀다보면 한 번의 상황에서 생길 수 있는 특정 경우를 모두 합쳐서 원하는 답을 계산하는 식으로 재귀를 이어나가 문제를 해결하는 경우가 굉장히 많다는 걸 알 수 있다. 해당 문제 또한 하루 동안 비가 오지 않는 경우와 비가 내릴 경우, 총 2가지 경우를 분할하여 각각을 재귀로 해결한 뒤 최종적으로 다시 합쳐 문제를 해결할 수 있다.

cache[depth][days] == 남은 days 동안 depth를 올라갈 수 있는 확률

cache[depth][days] = (0.75 * cache[depth - 2] [days -1]) + (0.25 * cache[depth -1] [days -1 ])

부분문제는 총 depth * days 만큼 발생하고, 하나의 부분문제당 상수시간만의 계산 횟수를 요하므로 시간복잡도는 O (Depth * Days) 이다. 따라서 문제에서 주어지는 최대 입력으로 계산한다면 대략 1백만 정도의 계산을 수행하는 알고리즘이고 1초의 시간제한이라면 충분히 해결할 수 있다.

기억하고 싶은 점

소수점을 출력하고자 하는데 자꾸 뒷부분 특정 자리수부터는 반올림되어 수가 잘려 출력되는 현상이 발생. cout으로 특정 자리까지 소수점을 출력하고 싶을 때 precision 함수를 통해 자리수를 지정하는 방법에 대해서 알게 되었다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>

using namespace std;

double cache[1001][1001];

double snail(int depth, int days) {
	if (depth <= 1) return (double)1;
	double& ret = cache[depth][days];

	if (ret != -1) return ret;
	if (depth <= 1) return ret = (double)1;
	if (days == 1) {
		if (depth >= 3) return ret = 0;
		else if (depth == 2) return ret = (double)3 / 4;
		else return ret = (double)1;
	}

	ret = (0.25 * snail(depth - 1, days - 1)) + (0.75 * snail(depth - 2, days - 1));

	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int testcase;
	cin >> testcase;
	while (testcase--) {
		int n, m;
		cin >> n >> m;
		fill_n(cache[0], 1002001, -1);
		double ret = snail(n, m);
		cout.precision(11);
		cout << ret << "\n";
	}
	return 0;
}