백준 9184 파이썬

2021.12.07

백준 9184 신나는 함수 실행

# 9184 ; 신나는 함수 실행
import sys

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 dp[a][b][c]:
        return dp[a][b][c]
    
    if a < b < c:
        dp[a][b][c] = W(a,b,c-1) + W(a,b-1,c-1) - W(a,b-1,c)
        return dp[a][b][c]
    dp[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 dp[a][b][c]
    
dp = [[[0 for i in range(21)] for i in range(21)] for i in range(21)]

while True:
    a,b,c = map(int, sys.stdin.readline().split())
    if a == -1 and b == -1 and c == -1:
        break
    print('w({}, {}, {}) = {}'.format(a,b,c,W(a,b,c)))

input()을 사용하기보다는 sys를 import 해서 시간 단축을 조금 더 해줬다.

다른 건 문제의 식을 전부 가져왔는데

중요한 아이디어는 삼차원 배열에 값을 저장해주는 것과

그 값이 있을 경우 바로바로 꺼내오는 것이 문제풀이의 핵심인 듯하다.

 

삼차원 배열에 저장해도 아래 코드를 쓰지 않으면 시간 초과가 뜬다.

    if dp[a][b][c]:
        return dp[a][b][c]

 

여담으로 아래 코드에서 공백을 안 넣어 줬더니 틀렸습니다만 계속 떠가지고 

뭐가 문제인지 한참을 찾았다...

print('w({}, {}, {}) = {}'.format(a,b,c,W(a,b,c)))