Boj 23846) 징검다리 건너기

문제

백준 23846

설명

확률이 들어가서 DP 식 짜기가 매우 헷갈리지만, 점화식 자체는 매우 간단하다.

i 번째 사람이 j+1 번째 징검다리를 성공적으로 지나갈 확률를 편의상 dp[i][j+1] 이라고 하자. 이 확률은 j 번째 발판에서 몇명이 실패했는지에 따라 세 경우로 구성할 수 있다.

• 아무도 실패하지 않았다면 이전 확률인 dp[i][j] 에서 1/3 을 곱한 값이다.
• 한명이 실패했다면 i-1 번째 사람이 j+1 번째 징검다리를 한번 실패하고 i 번째 사람이 남은 두 발판 중 맞는 발판을 고른 경우이다. 이 확률은 dp[i-1][j] * 2/3 * 1/2 이다.
• 두명이 실패했다면 j+1 번째 징검다리를 i-2 번째 사람이 처음 실패하고 i-1 번째 사람이 두번째로 실패해서 i 번째 사람이 남은 발판을 지나간 경우이다. 이는 dp[i-2][j] * 2/3 * 1/2 이다.

여기서 앞에 사람이 성공하면 뒷사람도 성공하므로 누적해서 값을 더해주면 답을 구할 수 있다.

시간 복잡도

O(\(\mathrm{N}\mathrm{K}\))

코드

double dp[500][3001];

int main()
{
	int n, k; cin >> n >> k;

	const double p = 1.0 / 3.f;

	dp[2][0] = 1;
	for (int i = 2; i < k+2; i++)
		for (int j = 0; j < n; j++)
			dp[i][j + 1] = (dp[i][j] + dp[i-1][j] + dp[i-2][j]) * p;
	
	double ans = 0; 
	for (int i = 2; i < k+2; i++) ans += dp[i][n];

	fixed(cout);
	cout << setprecision(17) << ans;//
}