백준 #31947 사다리 게임 만들기

문제 링크

[31947 사다리 게임 만들기]

문제 설명

$N$개의 세로선으로 구성된 사다리에 $M$개의 가로선을 추가한다. 이때 가로선이 각 세로선 사이에 추가될 확률은 모두 동일하다. $M$개의 가로선이 전부 추가된 후에 당첨될 확률을 구하는 문제.

코드

import sys
input = sys.stdin.readline


N, M = map(int, input().split())
S, E = map(int, input().split())
S -= 1
E -= 1
# dp[i][j]: j번째 가로선이 추가되었을 때 i번째 세로선의 우승확률
dp = [[0] * (M + 1) for _ in range(N)]
dp[E][0] = 1
for j in range(1, M + 1):
    for i in range(N):
        if i == 0:
            dp[i][j] = (dp[i + 1][j - 1] + (N - 2)* dp[i][j - 1]) / (N - 1)
        elif i == N - 1:
            dp[i][j] = (dp[i - 1][j - 1] + (N - 2) * dp[i][j - 1]) / (N - 1)
        else:
            dp[i][j] = (dp[i + 1][j - 1] + (N - 3) * dp[i][j - 1] + dp[i - 1][j - 1]) / (N - 1)


print(dp[S][-1])

풀이

$dp[i][j]$를 $j$번째 가로선에 추가되었을 때 $i$번째 세로선의 우승 확률이라 정의한 후에 동적 계획법으로 채워나갔다. 특정 세로선을 기준으로 자기 양옆에 가로선이 추가 될 때만 주의해주면된다. 오른쪽에 추가될 경우 추가되기 전의 오른쪽 세로선의 우승확률과 동일하고 왼쪽에 추가될 경우 추가되기 전의 왼쪽 세로선의 우승확률과 동일하다.

여태까지 사다리게임이 공정한줄 알았는데 아니였다…충격 당첨되는 세로선을 고를수록 당첨확률이 올라가는거였다니…ㅋㅋㅋㅋㅋㅋ 대박 앞으로 유용하게 써먹어야겠다.