[백준] 13703-물벼룩의 생존확률(C++)

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

13703번: 물벼룩의 생존확률

 

dp문제이고 top-down방식으로 해결하였다.

 

접근방식

 

1. 모든 경우를 고려해야 하는데 브루트 포스로는 시간초과가 날 것같다

즉, dp로 해결하는 문제

 

2. top-down방식으로 쉽게 해결이 가능하다.

 

 

문제풀이 

 

1.  높이 수면에 닿는 경우는 항상 배제시켜주고, 

시간이 다 될때 까지 수면에 닿지 않았다면 + 1 을 추가해주는 형태로 진행함

 

정답코드

 

#include <iostream>
using namespace std;

long long dp[64 * 2][64];
int n, k;

long long solved(int kk, int nn) {
	
	if (kk == 0)
		return 0;
	if (nn == 0)
		return 1;

	long long& ret = dp[kk][nn];
	if (ret != -1)
		return ret;
	ret = 0;

	ret += solved(kk-1, nn-1);
	ret += solved(kk+1, nn-1);

	return ret;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);

	cin >> k >> n;

	for (int i = 0; i < 64*2; i++)
		for (int j = 0; j < 64; j++)
			dp[i][j] = -1;

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

	return 0;
}