[python] algospot SNAIL

문제

깊이가 n 미터인 우물의 맨 밑바닥에 달팽이가 있습니다. 달팽이의 움직임은 그 날의 날씨에 좌우됩니다. 만약 비가 내리면 달팽이는 하루에 2미터를 기어올라갈 수 있지만, 날이 맑으면 1미터밖에 올라가지 못합니다. 앞으로 m 일간 각 날짜에 비가 올 확률이 정확히 75%일 전망입니다. m 일 안에 달팽이가 우물 끝까지 올라갈 확률을 계산하는 프로그램을 작성하세요.

-> 문제 링크 : https://algospot.com/judge/problem/read/SNAIL

algospot.com :: SNAIL

 

문제풀이

이 문제는 부분 문제로 쪼갤 수 있다.

만약 100일간 200m를 올라가야 하는데 99일날 198m 위치에 있다고 하자.

그럼 이때 99일 198m에서는 75%확률로 200m로 성공하고, 25%확률로 199m로 실패한다.

99일이고 198m일 때 끝까지 올라갈 확률은 0.75 * 1 + 0.25 * 0으로 0.75가 된다.

그렇다면 100일간 200m를 올라가야 할 때 0일날 0m위치에 있다면

이때 성공할 확률은 0.75 * 99일간 198m를 올라갈 확률 + 0.25 * 99일간 199m를 올라갈 확률이 된다.

 

즉, (남은 일, 올라간 m)를 기준으로 부분문제를 쪼갤 수 있게 된다.

(x, y) = 0.75 * (x,y+2) + 0.25 * (x,y+1)

 

이를 코드로 작성하고 메모이제이션을 적용해주면 된다.

코드

import sys

def snail(days, climbs) :

    if days == M :
        if climbs >= N :
            return 1
        else :
            return 0

    if dp[days][climbs] :
        return dp[days][climbs]

    ret = snail(days + 1, climbs + 1) * 0.25 + snail(days+1, climbs+2) * 0.75

    dp[days][climbs] = ret

    return dp[days][climbs]



# 1개
T = int(sys.stdin.readline().rstrip())

for _ in range(T) :

    N, M = map(int, sys.stdin.readline().rstrip().split(" "))
    dp = [ [None for _ in range(1001)] for _ in range(2001)]
    print( snail(0,0) )

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.