[백준/BOJ] 13703 물벼룩의 생존 확률

문제 : 13703 물벼룩의 생존확률

13703번: 물벼룩의 생존확률

1초마다 1/2 확률로 위 또는 아래로 이동할 때,

시간이 끝날 때까지 생존해있는 경우의 수를 구하면 된다.

수면에 닿았을 때 남은 움직임과 상관없이 모두 실패하고

남은 움직임 횟수보다 더 깊이 있는 상태에서는 2^횟수만큼 성공하므로

memoization기법을 활용해 Top-Down 방식의 DP를 짜서

이전 결과 값을 저장해 꺼내서 출력했다.

---

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll N, M, arr[70][70];
ll DP(ll now, ll x){
    if (arr[now][x]!=-1)
        return arr[now][x];
    else if (x<now)
        return pow(2,x);
    else if (now==0)
        return 0;
    else
        return arr[now][x]=DP(now+1,x-1)+DP(now-1,x-1);
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> N >> M;
    fill(&arr[0][0],&arr[69][70],-1);
    cout << DP(N,M);
    return 0;
}