[알고리즘]Algospot_SNAIL

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

문제

깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데, 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다.

여름 장마가 찾아와, 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하세요.

정정: 이 문제의 내용은 알고리즘 문제해결 전략 8.11에 나온 문제 설명과 약간 다릅니다. 책과 반대로 여기에서는 비가 내릴 경우 2미터, 맑을 경우 1미터를 올라가게 됩니다. 신고해주신 조성현님께 감사드립니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C(1≤C≤50) 가 주어집니다. 그 후 각 줄에 우물의 깊이 n(1≤n≤1000)과 장마 기간의 길이 m(1≤m≤1000) 이 주어집니다.

출력

각 테스트 케이스마다 한 줄에 m일 안에 달팽이가 우물을 탈출할 수 있을 확률을 출력합니다. 10−7 이하의 상대/절대 오차가 있는 답은 정답으로 인정됩니다.

정답코드

#include<bits/stdc++.h>
#define FASTio ios_base :: sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define endl '\n'

using namespace std;

int n,m;
double cache[1001][2002];

double jangmaIscomming(int day, int climb)
{
    if(day==m)
    {
        if(climb >= n) return 1;
        return 0;
    }

    double& ret = cache[day][climb];

    if(ret!=-1.0) return ret;

    return ret = 0.75*jangmaIscomming(day+1,climb+2) + 0.25*jangmaIscomming(day + 1,climb+1);
}


int main()
{
    FASTio;

    int t;

    cin >> t;


    while(t--)
    {
        for(int i=0; i<1001; i++)
        {
            for(int j=0; j<2002; j++)
            {
                cache[i][j]= -1.0;
            }
        }

        cin >> n >> m;

        cout << fixed;
        cout.precision(10);

        cout << jangmaIscomming(0,0) << endl;
    }

    return 0;
}

풀이 및 사고과정

책과 문제풀이사이트의 문제가 달라서 흠칫했지만 꽤 간단하게 풀었던 문제였다.
double자료형에서는 memset()함수가 안된다는 것을 몰라서 삽질을 했다.