[ALGOSPOT] SNAIL

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

algospot.com :: SNAIL

<문제>

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

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

 

<입력>

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

 

<출력>

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

 

<예제 입력>

4

5 4

5 3

4 2

3 2

 

<예제 출력>

0.9960937500

0.8437500000

0.5625000000

0.9375000000

 

 

쉬운듯 헷갈린듯 뇌절한 문제.

아니 이 쉬운 걸 왜 뇌절했지;

삼각형 경로 합 최대 찾는 문제랑 이 문제랑 다른 점이 없는데 왜 이 문제에 뇌절이 왔을지...

 

<아이디어>

앞서 말한 바와 같이 삼각형 경로 합 최대 찾는 문제와 매우 흡사하다.

base case : 장마가 끝나는 m일에 도달했을 때.

이때 움직인 거리가 n보다 크면 1 return, 작으면 0 return

 

그리고 이제 메모이제이션 해주면 된다.

dp[day][length] 로 메모이제이션 해준다.

 

 

내가 뇌절한 부분은 항상 비슷하다. 중복 계산하는 걸 어떻게 처리하는 지...

어떤 위치에서 어떻게 중복 계산되고 있는 지 알고있다.

DP는 그 중복되는 계산을 메모이제이션하여 다시 계산하지 않도록 하는 것인데 왜 자꾸 헷갈려하는 지 모르겠다.

 

 

#include <bits/stdc++.h>
using namespace std;
#define swap(a,b) (a)^=(b)^=(a)^=(b)
#define endl '\n'
typedef long long lld;
 
int n, m;
 
double top_down(vector<vector<double>>& dp, int day, int length)
{
    if(day==m) return length >= n? 1:0;
    double& ret = dp[day][length];
    if(ret!=-1.0) return ret;
    return ret = 0.25*top_down(dp, day+1, length+1)+0.75*top_down(dp, day+1, length+2);
}
 
int main()
{
    
    int tc;
    scanf("%d", &tc);
    while(tc--)
    {
        scanf("%d %d", &n, &m);
        vector<vector<double>> dp(m+1, vector<double> (2*n+1, -1.0));
        printf("%.8f\n", top_down(dp, 0, 0));
 
    }
    return 0;
}