[백준] 13703. 물벼룩의 생존확률 - Python

[Gold V]

 

https://www.acmicpc.net/problem/13703

 

풀이

재귀와 DP를 이용해 쉽게 풀이할 수 있는 문제.

 

loc(location, 물벼룩의 위치)가 0이 되면, 2에 남은 시간만큼의 제곱을 해 준다. (그만큼의 확률을 가져가므로) (line 9)

memoization을 이용하지 않고 재귀로만 풀이하면 시간초과가 난다.

 

AC.

k, n = map(int, input().split())
dp = [[-1]*200 for _ in range(200)]

def swim(sec: int, loc: int):
    if dp[sec][loc] != -1:
        return dp[sec][loc]
    
    if loc == 0:
        dp[sec][loc] = 2**sec
        return 2**sec
    if sec == 0:
        return 0

    dp[sec][loc] = swim(sec-1, loc-1) + swim(sec-1, loc+1)
    return dp[sec][loc]

swim(n, k)
print(2**n - dp[n][k])