[알고리즘 문제해결전략] SNAIL - 달팽이

[생각의 흐름]

1. 비오는날(75%)와 비가오지 않는날(25%)을 구분한다.

2. 비오는날과 비가오지 않는 날의 확률을 각각 곱하면서 목적지 (n)에 도달할 때까지 반복해 본다. => 완전탐색

3. 중복되는 경로의 확률을 메모이제이션 한다.

4. m일 안에 목적지 n에 도달했을 경우 1을 리턴하여 모든 경로의 확률을 곱하고 그렇지 않은 경우 0을 리턴하여 경우를 무효화 시킨다.

5. 절대 도달할 수 없는 경우( 예) 1000미터 우물을 100일 안에 도달)는 sol함수를 호출하지 않고 수식으로 가지치기 한다.

 

/* https://www.algospot.com/judge/problem/read/SNAIL */
#include <stdio.h>

const int MAX_DAYS = 1001;
const int MAX_METER = 2002;
int n, m;

// x일 동안 y미터 이동했을 때의 확률을 캐싱한다.
double cache[MAX_DAYS][MAX_METER];

double sol(int days, int totMeter)
{
    if (days == m)
    {
        if (totMeter >= n)
            return 1;
        else
            return 0;
    }

    double &ret = cache[days][totMeter];
    if (ret != -1.0)
    {
        return ret;
    }
    ret = 0;

    // 비가올 확률과 비가오지 않을 확률을 나눠서 더한다.
    ret = (sol(days + 1, totMeter + 2) * 0.75) + (sol(days + 1, totMeter + 1) * 0.25);

    return ret;
}

void resetCache()
{
    for (int i = 0; i < MAX_DAYS; i++)
    {
        for (int j = 0; j < MAX_METER; j++)
        {
            cache[i][j] = -1.0;
        }
    }
}

int main(void)
{
    int TC;
    scanf("%d", &TC);

    while (TC--)
    {
        scanf("%d %d", &n, &m);
        resetCache();

        // 절대 도달할 수 없는 경우는 속도 개선을 위해 가지치기 한다.
        if (2 * m < n)
            printf("%.10f\n", 0.0);
        else
            printf("%.10f\n", sol(0, 0));
    }

    return 0;
}