[Baekjoon] 9184번 : 신나는 함수 실행 (Python)

[Baekjoon] 9184번 : 신나는 함수 실행 (Python)

 

목차

 

https://www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

 

Python

 

방법 1 - 메모리 30864KB / 시간 100ms / 코드 길이 619B

DP 즉, 다이나믹 프로그래밍은 재귀 + Memorization이다.

본 문제는 재귀함수를 주고 어떻게 Memorization할 것인지를 물어보는 문제이다.

 

다만 주의점은 2가지가 존재한다.

1) a,b,c의 입력을 받을 때 input으로 받을 때와 sys.stdin.readline으로 받을 때 2가지가 존재하는데 후자가 더 빠르다.

전자의 경우 1000ms가 나온 반면 후자는 100ms가 나왔다.

2) Memorization을 하는 list가 공통으로 사용된다면 반복문 밖에 전역리스트로 선언하는 것이 좋다.

만약 아래 코드에서 while 문 안에 memorization을 위한 list를 넣었다면 새로운 a,b,c 마다 새롭게 저장해야하고 그만큼 시간이 더 걸린다. 이는 시간 초과를 초래할 수 있다.

 

import sys

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 l[a][b][c]:
        return l[a][b][c]
    elif a<b<c:
        l[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        l[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 l[a][b][c]

l = [[[0 for _ in range(21)] for _ in range(21)] for _ in range(21)]
while 1:
    a,b,c = map(int, sys.stdin.readline().split())
    if a == b == c == -1:
        break
    print('w(%d, %d, %d) = %d' %(a, b, c, w(a, b, c)))