1. 문제 설명
걷기 전에 동전을 던진 다음, 앞 면이면 왼쪽으로 한 칸, 뒷 면이면 오른쪽으로 한 칸 이동하는 방법을 랜덤 걷기라고 한다. 이 랜덤 걷기의 위치의 기댓값은 항상 0이 된다. 즉, 랜덤 걷기를 아무리 많이 한다고 해도, 평균 위치는 처음 시작한 지점과 같다.
랜덤 걷기에서 왼쪽으로 갈 확률과 오른쪽으로 갈 확률, 그리고 동전을 던지는 횟수가 주어졌을 때, 가장 오른쪽 위치의 기댓값을 구하는 프로그램을 작성하시오.
- 입력
첫째 줄에는 테스트 케이스의 P가 주어진다. 각 테스트 케이스는 모두 독립적이다.
각 테스트 케이스는 한 줄로 이루어져 있다. 이 줄에는 총 세 개의 숫자가 주어지는데, 왼쪽부터 순서대로 n, L, R이다. n(1 ≤ n ≤ 1000)은 동전을 던지는 횟수이다. L과 R은 각각 왼쪽으로 갈 확률과 오른쪽으로 갈 확률이다. ( 0 ≤ L ≤ 1, 0 ≤ R ≤ 1, 0 ≤ L+R ≤ 1) 이 문제에서 사용하는 동전은 조금 독특해서, 앞 면과 뒷 면이 나올 확률이 서로 다를 수도 있다. 또, 1-L-R은 동전의 옆 면이 나올 확률로, 옆 면이 나온 경우에는 그 자리에 그대로 있는다.
- 출력
각 테스트 케이스에 대해서, 가장 오른쪽 위치의 기댓값(평균)을 소수점 넷째 자리 까지 출력한다.
2. 문제 접근
DP는 DP인데 문제 풀이를 위한 점화식 접근이 매우매우 어려웠던 문제입니다.
.. 해서 구글링을 좀 했습니다!
문제의 원형은 Random Walk이라는 수학의 확률론적 개념에 근거합니다. (링크) 하지만 안타깝게도 Random Walk은 앞으로 갈 확률과 뒤로 갈 확률이 0.5로 같음이 전제이므로 적용하기 조금 힘들 수 있습니다.
그래서 찾은 링크가 여깁니다. www.reddit.com/r/dailyprogrammer/comments/16dbyh/011113_challenge_116_hard_maximum_random_walk/
DP를 2차원 배열로 놓고, DP[i][j] 를 i번 이동했고, j번 이동 기회가 남았을 때 이동할 수 있는 가장 먼(rightmost) 거리로 놓습니다. 따라서 0번째 row의 값을 DP[0][j] = j로 놓을 수 있습니다. 이론상 j번 오른쪽으로 이동할 수도 있으니까요.
앞면이 나올 확률을 head, 뒷면은 tail, 옆면은 side로 하겠습니다.
각 이동 기회에서 세 가지 경우의 수가 있습니다.
-
이동하지 않는 경우 : 움직이지 않으므로 거리의 기대치도 변하지 않습니다.
DP[i][j] += DP[i-1][j] x side -
왼쪽으로 이동한 경우 : 한 칸 왼쪽으로 거리의 기대치가 1 줄어듭니다.
거기다 오른쪽으로 한 번 더 이동해서 원래 위치로 다시 가야 동전을 던지기 전의 기대치와 같아집니다. 동전을 한 번 던지기 전 + 기회가 한 번 더 있는 상황입니다.
DP[i][j] += * (DP[i-1][j+1] - 1) x tail -
오른쪽으로 이동한 경우 : 한 칸 오른쪽으로 가서 거리의 기대치가 1 증가합니다.
왼쪽으로 이동한 경우와 반대로 생각해 줍니다. 동전을 던질 기회를 한 번 아꼈다고 볼 수 있습니다.DP[i][j] += * (DP[i-1][j-1] - 1) x tail
j가 0인 경우는 : 이동 횟수를 모두 소진한 경우입니다. j - 1 이 인덱스에서 벗어나기도 하고, i번 이동한 뒤 head가 나와 한 칸 더 앞으로 이동할 확률 -> DP[i][0] += (DP[i-1][0] + 1) x tail이므로
자바는 소수점 처리가 특이해서 round 함수를 쓰거나 Math.format, printf 등을 사용하면 특정 케이스에서 반올림으로 인해 소수점 오류가 납니다. 제 경우엔 DecimalFormat을 사용하니 오류가 나지 않았습니다.
3. 문제 풀이
- 자바
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.text.DecimalFormat;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int toss;
static double tail, head;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
while (T --> 0) {
st = new StringTokenizer(br.readLine());
toss = Integer.parseInt(st.nextToken());
tail = Double.parseDouble(st.nextToken());
head = Double.parseDouble(st.nextToken());
DP();
}
}
// DP 의 정의는 다음과 같음
// DP[i][j] : i번 이동했고, j번 이동 횟수 남았을 때 최상의 상황에서 가능한 오른쪽 끝 쪽 위치
// DP[0][i] : i번 던질 수 있고, 이동하지 않았으므로 최상의 경우 i번 오른쪽 이동 -> DP[0][i] = i
static void DP() {
double side = 1D - tail - head;
double[][] DP = new double[toss + 1][toss + 1];
for (int i = 0; i <= toss; i++) DP[0][i] = (double) i;
for (int i = 1; i <= toss; i++) for (int j = 0; j <= toss - i; j++)
DP[i][j] = side * DP[i-1][j]
+ tail * (DP[i-1][j+1] - 1)
+ head * (DP[i-1][Math.max(j-1, 0)] + 1);
DecimalFormat format = new DecimalFormat("0.0000");
System.out.println(format.format(DP[toss][0]));
}
}- 파이썬
def DP(toss, tail, head):
DP = [[0] * (toss + 1) for _ in range(toss + 1)]
for i in range(toss + 1): DP[0][i] = i
for i in range(1, toss + 1):
for j in range(toss - i + 1):
DP[i][j] = (1 - tail - head) * DP[i-1][j] + tail * (DP[i-1][j+1] - 1) + head * (DP[i-1][max(j-1, 0)] + 1)
print(f'{DP[toss][0]:.4f}')
T = int(input())
for _ in range(T):
toss, tail, head = map(float, input().split())
toss = int(toss)
DP(toss, tail, head)