[동적계획법/DP] 백준 9184 신나는 함수 실행 - 파이썬(Python)

 

[ Contents ]

 

 

1. 문제 (링크 참조)

9184번: 신나는 함수 실행

 

 

 

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)

 위 규칙대로 w(a, b, c) 함수를 구현하는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 단순 재귀만 사용하면 당연히 시간초과가 납니다. DP를 사용해서 이미 계산했던 w(a, b, c)는 불러와서 사용합니다.

 

 

 

3. 코드

import sys
input = sys.stdin.readline

cache = [[[0]*21 for _ in range(21)] for _ in range(21)]
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 cache[a][b][c]:  # 캐시값이 있으면, 캐시값 반환
        return cache[a][b][c]
    elif a < b < c:
        cache[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
        return cache[a][b][c]
    else:
        cache[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 cache[a][b][c]

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

 3차원 리스트를 캐싱해야하는 문제입니다. 그래도 21*21*21로 그렇게 큰 메모리 할당은 아닙니다.

 a, b, c가 음수이거나 20을 넘어서면 캐싱의 범위를 벗어나므로 그대로 처리를 해줍니다. 메모이제이션은 1~20 범위 안의 w(a, b, c)만 해줘야 합니다.