백준 9184 : 신나는 함수 실행 (파이썬)

신나는 함수 실행 

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	20643	8926	6757	42.008%

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

제한

• -50 ≤ a, b, c ≤ 50

예제 입력 1

1 1 1
2 2 2
10 4 6
50 50 50
-1 7 18
-1 -1 -1

예제 출력 1

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

---

코드

# https://teching.tistory.com/
import sys

memoization = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]
def w(a, b, c):
    global memoization
    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 memoization[a][b][c] == 0:
        if a < b and b < c:
            memoization[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        else:
            memoization[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 memoization[a][b][c]


for line in sys.stdin:
    A, B, C = map(int, line.split())
    if A == -1 and B == -1 and C == -1: break
    print(f"w({A}, {B}, {C}) = {w(A, B, C)}")

해설

단순하게 문제의 정답을 구하는 방법은 크게 2가지 방법으로 구현을 할 수 있다.

1. 순수 재귀함수 이용(분할 정복 알고리즘)
   구현하기엔 가장 쉽다. 하지만 시간이 매우 오래 걸린다는 단점이 있음.
   그러므로 해당 문제에서는 사용하면 시간초과가 발생한다.
2. 동적 계획법 이용
   1번의 방법보다는 구현하기 어렵지만 시간이 매우 단축된다!

동적 계획법이란?

기본적인 접근 방식은 분할 정복 알고리즘과 비슷하다. 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결괏값을 이용해 원래 문제의 답을 산출한다. 차이점은 동적 계획법은 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한번만 계산하고 저장해둔 뒤 다시 한 번 해당 문제를 풀때에는 저장해둔 답을 바로 산출하여 속도를 향상한 것이다.

즉, 이전에 계산했던걸 저장한다!! 저장이 핵심 포인트다!

동적 계획벅을 구현하는 방법은 2가지가 있다.

1. 하향식으로 문제를 풀어나가는 메모이제이션(Memoization) (주의 :메모라이제이션(Memorization) 아님!!)
2. 상향식으로 문제를 풀어나가는 타뷸레이션(Tabulation)

위의 코드는 메모이제이션를 이용하여 구현한 방법이다.

타뷸레이션 방법을 사용하면 필요없는 중간 값까지 전부 계산을 해주어야 해서 매우 번거롭기 때문이다!