백준 9184번: 신나는 함수 실행 (Python)

접근

동일한 계산을 반복해야 할 때, 이전에 계산한 값을 저장함으로써 동일한 계산 반복 수행을 제거하는 문제이다.

실질적으로 계산이 되는 범위는 각 숫자가 1에서 19일 때까지이므로 해당 범위에 대한 list를 만들어주고, 함수를 순환하는 중에 해당하는 값을 list에 저장해준다.

코드

import sys


wt = [[[0] * 21 for _ in range(21)] for __ in range(21)]


def w(a, b, c):
    global wt
    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 wt[a][b][c]:
        return wt[a][b][c]
    if a < b < c:
        wt[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return wt[a][b][c]
    wt[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 wt[a][b][c]


while 1:
    n, m, p = map(int, sys.stdin.readline().split())
    if n == -1 and m == -1 and p == -1:
        break
    print('w({}, {}, {}) = {}'.format(n, m, p, w(n, m, p)))

더 생각해 볼 것?

w(1, 1, 1) 부터 w(20, 20, 20) 까지 모두 미리 계산해두고, 조건에 따라 값을 리턴해주는 방법으로 수행해도 백준에서 답안 제출 시 동일한 시간, 동일한 메모리를 사용한다.

# w(1, 1, 1) 부터 w(20, 20, 20) 까지 모두 계산하여 wt에 저장하는 코드
wt = []
for i in range(0, 21):
    wt.append([])
    for j in range(0, 21):
        wt[i].append([])
        for k in range(0, 21):
            if i == 0 or j == 0 or k == 0:
                wt[i][j].append(1)
            else:
                if i < j < k:
                    wt[i][j].append(wt[i][j][k - 1] + wt[i][j - 1][k - 1] - wt[i][j - 1][k])
                else:
                    wt[i][j].append(wt[i - 1][j][k] + wt[i - 1][j - 1][k] + wt[i - 1][j][k - 1] - wt[i - 1][j - 1][k - 1])

이 것이 백준 테스트 입력에 20 20 20을 넘는 값이 항상 존재하여 모든 값을 저장할 수 밖에 없게 만들기 때문인지 알아보아야 겠다. 즉, w(20, 20, 20)을 넘지 않는 값만 계산한다면 모든 값을 저장하는 것 보다 더 빠르게 계산 값을 리턴해줄지 확인할 방법을 찾아보아야 겠다.