Baekjoon 3946. 랜덤 걷기 / Python

3946. 랜덤 걷기

난이도 : 플래티넘 3
소요 시간 : 1시간
날짜 : 2025.01.05
언어 : 파이썬
알고리즘 유형 : dp

설명 보기전에 문제 풀어보러 가기

1. 문제 설명

1. 동전 던지는 횟수 N, 앞면이 나올 확률(왼쪽으로 갈 확률)L, 뒷면이 나올 확률(오른쪽으로 갈 확률)R 이 주어진다.
2. N번 동전을 던졌을 때, '전체 이동경로의 가장 오른쪽 위치'의 기댓값을 구하기
3. 옆면이 나올 수도 있고, 가만히 있는다.

2. 해결 방식

1. 2차원 dp
   • dp[i][j] = i개의 동전을 던졌을 때, 시작 위치가 j인 경우 가장 오른쪽 위치의 기댓값
2. 점화식 설명
   • l * (dp[i-1][j+1] - 1) : 왼쪽으로 이동할 확률 * (그 전 dp의 오른쪽 위치의 기댓값 - 1)
   • (1-l-r) * dp[i-1][j] : 가만히 있을 확률 * 그 전 dp의 오른쪽 위치의 기댓값
   • r * (dp[i-1][max(0, j-1)] + 1) : 오른족으로 이동할 확률 * (그 전 dp의 오른쪽 위치의 기댓값 + 1)
3. 구하는 것 : dp[n][0] = 동전 n번 던지고, 시작위치 0인 경우

3. 정답 코드

import sys;input = sys.stdin.readline

for _ in range(int(input())):
    n, l, r = map(float, input().split())
    n = int(n)

    dp = [[0] * (n + 1) for _ in range(n + 1)]
    for i in range(n + 1):
        dp[0][i] = i
    for i in range(1, n + 1):
        for j in range(n):
            dp[i][j] = l * (dp[i-1][j+1] - 1) + (1 - r - l) * dp[i-1][j] + r * (dp[i-1][max(0, j-1)] + 1)

    print(f'{dp[n][0]:.4f}')