백준 9148 신나는 함수 실행 - Python

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

9184번: 신나는 함수 실행

풀이 :

dp = [[[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
    if a > 20 or b > 20 or c >20 :
        return w(20,20,20)
    if dp[a][b][c]:   # 0 이면 반환을 안함
        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]

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

다이나믹 프로그래밍에 대해 이해가 부족해 해설을 참고했다.

하지만 이 문제로 인해 다이나믹 프로그래밍을 이해 할 수 있었다.

 

다이나믹 프로그래밍은 두 번 이상 계산 하지 않고 한 번 계산을 했으면 그걸 저장하고 다음 계산을 진행 시켜서 시간을 최소화 하는 프로그래밍인것을 살짝 느꼈다.(아닐지도..)

 

그래서 일단은 각각 a,b,c 에 대한 각각의 값을 저장해야하므로 list comprehesion 으로 dp 라는 3차원을 구현해준다.

 

그 다음 문제에 제시된 재귀함수를 만들어준다.

그리고 여기서 dp가 0 이 아니면 그냥 출력하게 하고 0이면 출력을 안하게 해준다.

 그리고 w값이 존재하면 그건 dp 에 저장해서 한 번계산한 내용에 대해서는 계속 그 값을 이용할 수 있게 해준다.