백준 - 랜덤 걷기(3946)

 

 

문제

 

다음과 같이 dp를 정의하자.

$\text{dp}[n,k]$ : $n$번 진행했을때 가장 오른쪽 위치가 $k$일 확률

 

$n$번의 이동은 ($1$번의 이동) + ($n-1$번의 이동)으로 나눌 수 있다.

이 아이디어를 적용해 다음과 같이 점화식을 구성할 수 있다.

$$
\text{dp}[n,k] =
p_\text{left} \cdot \text{dp}[n-1,k+1] +
p_\text{stay} \cdot \text{dp}[n-1,k] +
p_\text{right} \cdot \text{dp}[n-1,k-1]
$$

그런데, 가장 오른쪽의 위치가 $0$인 경우는 특별히 고려해 줄게 더 있다.

이유는 설명하지 않겠지만 결과를 이야기 하자면, $\text{dp}[n,0]$를 계산할때 $p_\text{left} \cdot \text{dp}[n-1,0]$를 더해줘야 한다. (참고로 $\text{dp}$ 정의에 따라서 $\text{dp}[n][\cdot]$의 합은 항상 $1$이여야 하는데, $(p_\text{left} \cdot \text{dp}[n-1,0])$를 더해주지 않으면 $\text{dp}[n][\cdot]$의 합이 $1$로 유지되지 않는다.)

 

$n$번 던졌을때 가장 오른쪽 위치의 기댓값은 기댓값의 정의에 따라

$$
\sum_{k=0}^{n} k \cdot \text{dp}[n,k]
$$

로 구하면 된다.

 

Plus

필수는 아니지만, 이 문제를 풀때 다음 문제로 바꾸어 풀어서 개인적으로 접근하기 더 쉬웠다.

 

$-1,0,1$을 각각 $p_\text{minus}, p_\text{zero}, p_\text{plus}$의 확률로 하나씩 선택해서 길이 $n$의 수열을 만들 것이다. 수열의 prefix sum값의 최댓값의 기댓값을 구하자.