알고리즘 백준 9184 신나는 함수 실행(파이썬)

알고리즘 백준 9184 신나는 함수 실행(파이썬)

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

백준 파이썬 신나는 함수 실행

 

문제

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

다음과 같은 재귀함수 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

 

코드

import sys


def w(a,b,c):
    # if emptyList[a][b][c] != 0:
    #     return emptyList[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)
    if emptyList[a][b][c] != 0:      #2)
        return emptyList[a][b][c]
    elif a<b and b<c:
        emptyList[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
        return emptyList[a][b][c]
    else:
        emptyList[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 emptyList[a][b][c]



if __name__ == '__main__':

  #  N = int(sys.stdin.readline())
    emptyList=[]
    number=0
    for i in range(21):          #1)
        outside=[]
        for k in range(21):
            inside=[]
            for j in range(21):
                inside.append(number)
            outside.append(inside)
        emptyList.append(outside)
   # print(emptyList)

    while True:
        a,b,c = map(int,sys.stdin.readline().split(" "))
        if a == -1 and b==-1 and c== -1:
            break
      #  w(a,b,c)
        print("w("+str(a)+", "+str(b)+", "+str(c)+") = "+str(w(a,b,c)))
     #   print(emptyList[a][b][c])

 

코드설명

0) 해당 문제는 재귀를 이용하는데 동적 프로그래밍처럼 메모라이젼을 사용하는 문제다 즉, 데이터를 저장한 리스트가 존재해야한다

0-1) 따라서 데이터를 저장할 3중리스트를 만들었고 a,b,c값이 20이 넘을경우에는 다 20으로 처리됨으로 크기를 20까지로 제한하였다

0-2) 문제에서 주어진 함수를 코드로 구현하였고 중간에 해당 값이 0일경우(데이터가없을경우)에만 데이터를 구하게 재귀가 돌며 값이 있을 경우에는 해당 값을 바로 반환하여 재귀의 숫자를 줄여 효율적인 프로그래밍이 되었다

 

 

1) #1) 코드는 데이터를 저장하기 위해 3중리스트를 짜는 코드이다.

 

2) #2) 코드는 처음에 3중리스트가 0으로 채워져있기 때문에 0이 아니면 해당 데이터가 이미 존재한다는 뜻임으로 해당 데이터를 반환하고 아니면 해당 데이터의 값을 찾기위해 재귀를 시작한다

 

깃허브

https://github.com/developer-hyun/Algorithm-Study/tree/main