Recursion

[백준] 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 ..

[백준] 1074. Z - 파이썬

https://www.acmicpc.net/problem/1074 풀이 재귀함수, 분할정복(Divide and Conquer)를 통해 어렵지 않게 풀 수 있었던 문제. 각 단계마다 4개의 구역으로 나누어, 어느 구역에 있는 지를 확인하고, 크기를 다시 1/4로 줄여 어느 구역에 있는 지를 확인하는 과정을 반복하면 된다. 와 같은 경우, N=2일 때 1행 3열의 숫자인 7을 구하는 과정은 (0행 0열이 start.) sol(2, 3, 1) 에서 middle = 2 이므로, r >= middle, c = middle 이므로 r = r - middle = 1 그리고 1구역이므로, 1x4 = 4 에, sol(N-1, r, c) 을 재귀호출하여 더해준다. 호출된 sol(1, 1, 1) 에서..