[BOJ] 3946번: Maximum Random Walk

https://www.acmicpc.net/problem/3946

맨 처음에는 D[t][a][b] : t번째 이동에 right most가 a이고 현재 위치가 b인 확률로 두고 식을 세우려고 했습니다. 이 경우 식은 직관적으로 뽑아낼 수 있는데 시간이 O(t^3)이라 다른 방법을 고민했습니다.

저는

D1[1003][1003]; // i번 이동했을 때, rightmost = 0을 만족하는 상태로 왼쪽 j칸에 있을 확률

D2[1003]; // i번 이동했을 때, rightmost = 0을 만족하는 확률

D3[1003]; // i번 이동했을 때 rightmost의 기댓값, 문제에서 요구하는 답

이라 두고, D1[i][j] = L*D1[i-1][j-1]+R*D1[i-1][j+1]+(1-L-R)*D1[i-1][j]으로 우선 D1을 구하고, D1을 이용해 D2[i] = sum(D2[i][0 to i])로 D2를 구하고, D2를 이용해

D3[i] = R * (1 + D3[i - 1]) + (1 - L - R) * D3[i - 1] + L * (D3[i - 1] - 1 + D2[i - 1]); 으로 D3을 구했습니다.

이렇게 풀긴 풀었는데 뭔가 더 쉬운 방법이 있을 것 같아 다른 사람의 코드를 보니

D[i][j] : 앞으로 a번 이동할 것이고 현재 b의 위치에 있을 때 rightmost의 기댓값이라고 정의했을 때

D[i][j] = L*(D[i-1][j+1]-1) + R*(D{i-1][max(j-1,0)]+1) + (1-L-R)*(D[i-1][j]))으로 계산이 가능했습니다.

https://github.com/blisstoner/BOJ/blob/master/3946.cpp