9184 문제 신나는 함수 실행 python - [백준-실버2/재귀함수]

문제 내용 요약

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)를 출력하는 프로그램을 작성하시오.

 

문제 원리파악

다이나믹 프로그래밍을 풀때 Top Down으로 풀어보자 

피보나치 수열 Top Down방식 참고하여 풀면 쉽게 이해하며 풀 수 있다.

d = [0] * 100

global count
count = 0

def fibo(x):
#     print(d)
    global count
    
    if x == 1 or x == 2:
        count += 1
        return 1
    
    # 이미 계산된 적이 존재하다면 pass
    if d[x] != 0:
        return d[x]
    
    count += 1
    d[x] = fibo(x - 1) + fibo(x - 2)
    
    return d[x]

문제풀이

Top Down으로 풀때 저장할 배열공간 정의

ls = []
for _ in range(21):
    ls_val = []
    for _ in range(21):
        ls_val2 = []
        for _ in range(21):
            ls_val2.append(0)
        ls_val.append(ls_val2)
    ls.append(ls_val)

저장된 값이 0이 아니면 재귀함수로 반복해서 재호출하지말고 저장된 곳에서 그 값을 리턴함

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:
        a, b, c = 20, 20, 20
        return w(a, b, c)
    
    # 만약 값이 ls[a][b][c]가 0이 아니고 값이 존재할시 그 값을 Return
    if ls[a][b][c] != 0:
        return ls[a][b][c]
    
    elif a < b and b < c:
        ls[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
    
    else:
        ls[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 w(a - 1, b, c) + w(a - 1, b - 1, c) + w(a - 1, b, c - 1) - w(a - 1, b - 1, c - 1)

이거 출력문도 다르게 하니까 틀리더라..조금 불편함

while True:
    a,b,c = map(int, input().split())
    if a ==-1 and b ==-1 and c ==-1:
        break
        
    res = w(a,b,c)
    print(f"w({a}, {b}, {c}) = {w(a,b,c)}")

 

이런식으로 출력하니 오답으로 나옴

while True:
     val = list(map(int, input().split())) 
     if val == [-1, -1, -1]:
        break
     else:
        val_ls.append(val)
        
     for a,b,c in val_ls:
         val = w(a, b, c)
         test = "w({0}, {1}, {2}) = {3}"
         print(test.format(a,b,c,val))