Maximum Random Walks

Maximum Random Walks

백준온라인 저지 3946번 문제입니다.

스터디에서 풀기로 했던 문제였는데 저한테는 너무 어려운 문제였습니다. 

문제 자체도 해석이 잘 안되었었는데요. 오히려 번역이 애매했습니다. 영문으로 된 설명을 스터디원 한테 들은 이후에야 문제가 이해가 갔습니다.

(문제가 이해가 가는 것과 푸는 것은 또 별개였습니다. 2시간 반 넘게 고민했지만 못 풀어서 그냥 답안을 보기로 하였어요. 이제 2시간 반이 넘게 걸리는 문제는 왠만해선 끝까지 안 물고 늘어지려구요, 답 보고 공부하는 게 저한텐 훨씬 나은 것 같습니다.)

문제는 다음과 같습니다.

동전 하나를 던질 때 뒷면이 나오면 왼쪽으로, 앞면이 나오면 오른쪽으로 걷습니다.

다만 동전이 옆면이 나오는 경우도 있는데 이 경우엔 움지기이지 않기로 합니다.

총 던지는 동전 수, 왼쪽으로 갈 확률, 오른쪽으로 갈 확률을 입력 받습니다.

결과 값으로 가장 오른쪽에 있을 확률을 리턴합니다.

이 때, 가장 오른쪽에 있을 기대 값 - 이라는 정의가 이해가 가질 않았었는데요.

예제에 있는 (4, 0.5, 0.5)로 보자면 이렇게 설명할 수 있습니다.

왼쪽 (이하 L), 오른쪽 (이하 R) 이라고 봤을 때, 4번 던진다면 총 16가지의 경우의 수가 나오게 됩니다. (여기서 확률은 0.5, 0.5 이므로 일단 무시하고 보겠습니다.)

L-L-L-L의 경우 왼쪽만 4번이 나오게 되는데요. 중간 시작 지점을 0이라고 봤을 때 0을 넘어선 적이 한 번도 없습니다. (-1이 4번인 거죠.)

이 때 가장 오르쪽으로 간 적이 없으니 0으로 보면 됩니다.

그렇다면 L-L-R-R의 경우는 왼쪽 2번 오른쪽 2번인데 어떻게 될까요?

이 때 역시 가장 오른쪽으로 간 적이 없습니다. (가장 오른쪽이라는 의미는 한 번이라도 시작 지점의 오른쪽을 넘어섰다는 것으로 보면 됩니다.)

이 경우 역시 0으로 봅니다.

다른 경우를 보죠.

R-L-L-L의 경우는 결과가 1이 됩니다. 마지막 포지션은 0 이하지만 이미 처음 스텝에서 오른쪽으로 갔으므로 (+1) 가장 오른쪽에 있던 경우는 1이 되는 것입니다.

또 다른 경우를 보겠습니다

R-R-R-L 입니다. 이 경우는 3이 됩니다. 마찬가지로 첫 스텝에서 현재 온 것 중에 가장 오른쪽이었으므로 +1, 그 다음 스텝에서 마찬가지로 +1, 마지막으로 +1 입니다.

R-R-R-R은 4고, R-R-L-L은 2입니다.

이런 식으로 전체 경우를 다 보면 19가지가 나오고 동전의 왼쪽, 오른쪽이 나올 모든 경우의 수가 16이므로 (옆면은 제외합니다. 확률에 없었으니까요) 19 / 16 으로 1.1875입니다.

저는 처음에 이 문제를 왼쪽 -1, 오른쪽 +1로 해서 한 번이라도 양수가 되는 경우를 카운트 하되, 결과가 중복되는 경우를 제외하기로 했었는데요.

이 때 양수가 되는 경우에서 오른쪽이 두번 나오면 오른쪽 확률 ^ 2 형식으로 따로 분모를 만들고 거기에 총 카운트를 곱한 후 전체 경우의 수를 다 더하면 나올 줄 알았습니다.

그런데 잘 안되서 (라고 쓰고 구현을 못해서)

그러다가 중간에 경우의 수를 각각 왼,오, 가운데 로 나눈 후 각각 나올 확률을 따로 곱해서 총 더한 후의 결과면 또 될 줄 알았습니다.

결과적으로는 못했어요. 2시간이 넘게 지남 ㅠㅠ

그래서 그냥 답안을 찾아보기로 하였습니다. 기왕이면 파이썬이 좋아서 파이썬으로 찾았고 그렇게 해서 아래의 코드를 보게 되었습니다.

import sys ; sys.setrecursionlimit(2000)

cache = {}
def walk(n, L, R, f=0):
    if n == 0: return f
    key = n, L, R, f
    if key not in cache:
        EL = walk(n-1, L, R, f+1) - 1
        E0 = walk(n-1, L, R, f)
        ER = walk(n-1, L, R, max(f-1, 0)) + 1
        cache[key] = L * EL + R * ER + (1-L-R) * E0
    return cache[key]

(출처 : https://www.reddit.com/r/dailyprogrammer/comments/16dbyh/011113_challenge_116_hard_maximum_random_walk/)

(DP로도 풀 수 있고, 메모이제이션으로 할 수도 있는데 작성자는 메모이제이션으로 했다고 하였습니다.

아래의 답변들 보면 C로 푼 DP도 있으니 보면 좋을 것 가습니다.)

작성자가 친절히 코드를 설명해주셨습니다.

못하는 영어로 해석해보면 아래와 같습니다.

(일단 단순하게, L과 R 값을 고정하겠다.) 당신이 방문한 가장 오른쪽의 위치를 flag라고 정의한다. 당신이 서 있는 flag에서 만약 오른쪽으로 간다면 당신은 flag를 데려온다. 다시 보면 당신이 왼쪽으로 간다면 당신은 flag 뒤에 서 있게 된다. 그럼 n번 움직였을 때 flag의 위치는 어디가 되는가?

• 이 말인즉슨 오른쪽으로 이동한다면, flag_new = flag + 1이 되고 flag = falg_new - 1이 된다는 의미입니다.

walk(n,f)는 당신이 현재 0에 서 있게 된다면 갖게 되는 flag의 마지막 위치이다. 그러니까 당신이 k에 서 있게 된다면 마지막 flag의 위치는 walk(n,k-k)+k 가 된다.

이것을 세 가지 경우로 나누어서 보겠다.( n 은 steps 입니다. )

첫째, 동전 옆면(움직일 수 없는 경우)이 나온다면 E0 = walk(n-1, f)가 된다.

둘째,  왼쪽으로 (현재 턴에서)가는 경우 k는 -1이 되므로 EL = walk(n-1, f+1) -1 이 된다.

마지막으로,  오른쪽으로 (현재 턴에서)가는 경우 k는 +1이 되므로 ER = walk(n-1, f-1)  +1 이 된다.

일단 flag는 절대로 당신의 왼쪽에 있을 수 없다. 우리는 가장 오른쪽에 있을 경우만 구해야 하기 때문이다. 그래서 f-1을 max(f-1,0)으로 바꾸자. (이 의의미는 현재 포지션/flag 가 음수인 경우를 제외하고자 한 것 같습니다. 가장 오른쪽에 있는다는 의미는 0보다 커야 하는 경우만 세야 하기 때문이죠.)

그럼 마지막으로 공식은

walk(n-f) - L * EL + R * ER + (1-L-R) * E0 가 된다.

그리고 재귀로 해당 문제를 구현 하면 된다.

공식대로 풀이를 구현한 후, 중복 계산을 막기 위해 메모이제이션으로 푼 것을 볼 수 있었습니다.

근데 아무리 읽어도 이해가 가지 않더군요. 그래서 그냥 값을 다 넣어봤어요. (4, 0.5, 0.5) 를 넣으면서 거꾸로 계산해 보았습니다.

그러니까 실제로 리턴되는 f는 앞에서 제가 설명했던 가장 오른쪽에 있을 경우들 (R-R-R-L은 3이고 하는) 을 의미한다고 생각합니다.

아직 더, 보고 공부해야할 것 같아요.