(C++) - 백준(BOJ) 13703번 : 물벼룩의 생존확률 답

www.acmicpc.net/problem/13703

13703번: 물벼룩의 생존확률

dp문제였습니다.

 

풀이방법

생존할 경우 : 제한시간 n초 안에 수면에 가지 않을 때 생존 경우 수 추가

생존 경우 수 :  위로튈때 생존경우 수 + 아래로 내려갈때 생존경우 수

 

Code

#include <iostream>
#include <cstring>
#define ll long long
using namespace std;
ll height,second;
ll flee[1000][1000];

ll dp(ll k,ll n){
    ll &ret = flee[k][n];
    if(ret!=-1) return ret;
    if(k==0) return 0;
    if(!n) return 1;

    ret = dp(k+1,n-1) + dp(k-1,n-1);
    return ret;

}
int main(){
    cin >> height >> second;
    memset(flee,-1,sizeof(flee));
    cout << dp(height,second);
}