[2016 홍익대학교 프로그래밍 경진대회] 13703번 물벼룩의 생존확률

문제

수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다.  물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다.  예를 들어, 수면아래 2 센티미터에 있던 물벼룩은 3초동안 "위위위, 위위아래, 위아래위, ..., 아래아래아래"의 8가지 방법으로 움직일 수 있고, 이 방법들의 확률은 모두 1/8로 같다.  이 중, "위위위, 위위아래"의 경우 2초만에 수면에 닿자마자 먹혀 없어진다.  그리고 나머지 6가지 경우에는 수면아래에 살아있게 되어, 3초후 생존확률은 6/8이다.  수면아래 k 센티미터에 있는 물벼룩이 n초후 생존할 확률이 S/2n일때 S를 계산하시오.

입력

첫째 줄에 k와 n이 주어진다. (0 ≤ k ≤ n ≤ 63)

출력

첫째 줄에 S를 출력한다.

 

완탐으로 풀 수가 없었음.

0이되는 시점에서 -> 위

                        -> 아래

이렇게 두가지로 파생되므로 2개가 더해져야하는데 1개씩만 체크했고 2개를 더해도 그로부터 또 파생되는 것에 따라

또 달라지는 케이스가 발생.

따라서 dp로 풀어야한다.

 

도중에 깊이가 0이 되지 않고, time을 모두 소진했다면 개수 1개를 추가해주는 식으로 차곡차곡 올라오고,

어떤 depth에서 어떤 time일때 저장된 값이 있다면 그것을 반환해주어 중복 계산 방지.

 

#include<iostream>
#include<string>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<stack>
#include<set>
#include<map>
using namespace std;
int k, n;
const int depth = 63 * 2 + 1;
const int time = 63 + 1;
long long dp[depth][time];


long long dfs(int depth, int time)
{
	if (!depth)
		return 0;
	else if (!time)
		return 1;
	if (dp[depth][time] != -1)
		return dp[depth][time];
	dp[depth][time] = dfs(depth - 1, time - 1) + dfs(depth + 1, time - 1);
	return dp[depth][time];

}

int main() {
	ios_base::sync_with_stdio(false); 
	cin.tie(NULL);
	cin >> k >> n;

	memset(dp, -1, sizeof(dp));
	cout << dfs(k, n) << endl;
}