[🥈2 / 백준 9184 / 파이썬] 신나는 함수 실행

 

9184번: 신나는 함수 실행

 

문제

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

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

위의 함수를 구현하는 것은 매우 쉽다.

하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, 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 2 2 2 10 4 6 50 50 50 -1 7 18 -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

 

 

풀이

 

별로 신나진 않는 문제이다.

 

각설하고 문제에 나온 재귀 함수를 파이썬으로 구현해보자.

 

def w(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20,20,20)
    if a < b and b < c:
        return w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
    
    return 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,b,c 순서쌍에 대해서 이미 해를 구한 적이 있다면

계산 없이 바로 그 순서쌍에 맞는 해를 가져와 리턴해주도록 하자.

 

이를 구현하기 위해 딕셔너리를 이용할 것이다.

 

import sys
solve = {}

def w(a,b,c):
    if (a,b,c) in solve:
        return solve[(a,b,c)]
        # 이미 해를 구했다면 딕셔너리에서 가져온다.
        
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        return w(20,20,20)
    if a < b and b < c:
        solve[(a,b,c)] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        return solve[(a,b,c)]
    
    solve[(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 solve[(a,b,c)]

while(True):
    a,b,c = map(int,sys.stdin.readline().split())
    if a==-1 and b==-1 and c==-1:
        break
    print("w(%d, %d, %d) = %d" %(a,b,c,w(a,b,c)))