[Python/파이썬] 백준 알고리즘 9184번 - 신나는 함수 실행 (DP)

 

 

 

<풀이>

1. 아이디어
재귀 호출로 인한 시간복잡도를 줄여줄 수 있는 DP를 이용해야한다.
3차원 배열로 memoization을 만들면 되지 않을까..?
20 * 20 * 20의 공간만 있으면 된다.

2. 시간복잡도
- O(n^3) : 20 * 20 * 20 = 8000      -> 가능

3. 자료구조
a, b, c: int;
dp: int[][][];

 

전체코드 ↓

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline


def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    elif a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)
    elif dp[a][b][c]:
        return dp[a][b][c]
    elif a < b < c:
        dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return dp[a][b][c]
    else:
        dp[a][b][c] = w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)
        return dp[a][b][c]


while 1:
    a, b, c = map(int, input().split())
    if a == -1 and b == -1 and c == -1:
        break
    dp = [[[0] * 21 for _ in range(21)] for _ in range(21)]

    print("w({}, {}, {}) = {}".format(a, b, c, w(a, b, c)))

처음에 w()함수 각각에 대해서 dp 리스트에 있는지 확인하고 없다면 함수를 돌려 dp 리스트에 결과값을 넣고 있다면 그 값을 사용하려고 생각해서 애먹었다.

근데 그럴필요 없이 dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)와 같이 리스트에 값을 넣어준 뒤 dp[a][b][c]로 리턴하면 됐다.

elif dp[a][b][c]:
    return dp[a][b][c]

그리고 위의 조건을 잊으면 안된다..!

 

 

Top-Down(재귀 이용) 방식으로 DP문제를 잘 안풀어봐서 애먹었던 것 같다..!

더 연습해서 다져야겠다!!

 

 

 

<핵심 정리>

1. Top-Down 방식의 DP 구현에서는

# Top-Down 방식의 피보나치 함수 구현
num = int(input())

arr = [0] * (num + 1)
def fibonacci(num):
    if num == 0: return 0
    if num == 1: return 1
    if arr[num] != 0: return arr[num]
    arr[num] = fibonacci(num - 1) + fibonacci(num - 2)
    return arr[num]

print(fibonacci(num))

위와 같이 구현한다.

여기서 핵심은 if arr[num] != 0: return arr[num]과

arr[num] = fibonacci(num - 1) + fibonacci(num - 2)
return arr[num] 이다.

2. 변수가 3개면 3차원 배열을 memoization으로 사용하면 된다.