algospot SNAIL

문제 링크입니다: https://algospot.com/judge/problem/read/SNAIL

메모이제이션을 사용하면 쉽게 풀 수 있는 문제입니다.

/*

깊이가 height미터인 우물의 맨 밑바닥에 달팽이가 있다.

이 달팽이는 우물의 맨 위까지 기어올라가고 싶어하는데,

달팽이의 움직임은 그 날의 날씨에 좌우된다,

비가 오면 2미터 올라가고 날이 맑으면 1미터 올라간다.

앞으로 day일간 날짜에 장마가 찾아와 비가 올 확률이 75%라면

day일안에 달팽이가 우물 끝까지 올라가게 될 확률은?

*/

#include <iostream>

using namespace std;

 

const int MAX = 1000; //최대 1000일

int height, day;

double cache[MAX][2 * MAX]; //최대 2000m 갈 수 있으므로(매일 비가 왔을 경우)

//달팽이가 passed일 동안 climbed미터 기어올라 왔다고 할 때

//day일 전까지 height미터를 기어올라갈 수 있는 경우의 수

double climb(int passed, int climbed)

{

        //기저 사례:day일이 모두 지난 경우

        if (passed == day)

               return climbed >= height ? 1 : 0;

        //메모이제이션

        double &result = cache[passed][climbed];

        if (result != -1.0)

               return result;

        return result = (0.25 * climb(passed + 1, climbed + 1)) + (0.75 * climb(passed + 1, climbed + 2));

}

 

int main(void)

{

        int test_case;

        cin >> test_case;

        if (test_case > 50 || test_case < 1)

               exit(-1);

       

        for (int i = 0; i < test_case; i++)

        {

               cin >> height >> day;

               if (height < 1 || height>1000 || day < 1 || day>1000)

                       exit(-1);

               //double형이므로 memset 적용이 안됨

               for (int i = 0; i < 1000; i++)

                       for (int j = 0; j < 2000; j++)

                              cache[i][j] = -1.0;

               cout.precision(11); //10자리

               cout << climb(0, 0) << endl << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

[참고] 프로그래밍 대회에서 배우는 알고리즘 문제해결전략