백준 13703번 물벼룩의 생존확률

문제 링크입니다: https://www.acmicpc.net/problem/13703

간단한 DP 문제였습니다.

똑같은 확률로 1초당 한칸 위로 올라가거나 한칸 내려갈 수 있기 때문에 두 가지 모두 고려했습니다.

저와 다르게 시간을 오름차순으로 구해도 동일하게 답을 구할 수 있을 것 같습니다!

#include <iostream>

#include <cstring>

using namespace std;

 

const int DEPTHMAX = 63 * 2 + 1; //63에서 63초 뒤까지

const int MAX = 63 + 1;

 

int k, n;

long long cache[DEPTHMAX][MAX];

 

long long isAlive(int depth, int seconds)

{

        if (!depth) //수심 도달하면 잡아먹힌다

                 return 0;

        else if (!seconds) //시간 다 지나도 잡아먹히지 않아서 생존

                 return 1;

 

        long long &result = cache[depth][seconds];

        if (result != -1)

                 return result;

 

        //아래로 한칸, 혹은 위로 한칸

        result = isAlive(depth + 1, seconds - 1) + isAlive(depth - 1, seconds - 1);

        return result;

}

 

int main(void)

{

        cin >> k >> n;

       

        memset(cache, -1, sizeof(cache));

       

        cout << isAlive(k, n) << endl;

        return 0;

}

개발환경:Visual Studio 2017

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