[백준] 9184번 - 신나는 함수 실행 (DP) - 결과 포함

www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

다이나믹 프로그래밍 문제로

주어진 조건을 그대로 구현하면 실행 시간이 굉장히 오래 걸린다.

 

이럴 때 사용하는 것이 메모이제이션(Memoization) 기법이다.

캐싱(Caching)이라고도 부르는 이 기법은 중복된 연산을 피하고자 하는 다이나믹 프로그래밍을 위해서

기존에 계산한 결과를 저장해놓고 만약 다시 그 값이 필요하다면 곧바로 이미 저장되어있는 값을 반환하는 기법이다.

 

이 문제에서 입력으로 들어가는 변수는 a, b, c 세 가지이고

a, b, c 모두 -50 이상 50 이하라는 입력 조건이 있다.

 

a, b,c 중에 하나라도 0이하이면 바로 1을 반환하기 때문에

저장할 수 있는 결과는

a : 1 ~ 50

b: 1 ~ 50

c: 1 ~ 50

일 때 이고

총 50 x 50 x 50 가지의 경우의 수가 나온다.

 

재귀함수를 호출할 때 기존에 이미 계산했다면 배열에서 해당 값을 바로 반환해준다.

[소스 코드]

import sys

d = [[[0] * 51 for _ in range(51)] for _ in range(51)]


def w(a, b, c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if d[a][b][c] != 0:
        return d[a][b][c]
    elif a > 20 or b > 20 or c > 20:
        d[a][b][c] = w(20, 20, 20)
        return d[a][b][c]
    elif a < b < c:
        d[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return d[a][b][c]
    else:
        d[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 d[a][b][c]


while True:
    a, b, c = map(int, sys.stdin.readline().rstrip().split())

    if a == -1 and b == -1 and c == -1:
        break

    print('w({0}, {1}, {2}) ='.format(a, b, c), w(a, b, c))