[Python] 백준 - 9184 신나는 함수 실행

# 백준 Silver2

# 9184 신나는 함수 실행

 

[문제]

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

9184번: 신나는 함수 실행

 

 

[문제 풀이]

동적계획법

메모이제이션

- 재귀를 사용할 경우, 동일한 계산의 반복으로 시간 효율이 떨어진다.

- 계산한 결과를 메모리에 저장해두어 중복 계산을 방지할 수 있다.

 

[구현 코드]

import sys
MAX = 21
res = [[[0]*MAX for _ in range(MAX)] for _ in range(MAX)]

def w(a,b,c):
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a >= MAX or b >= MAX or c >= MAX:
        return w(20,20,20)
    # 이미 저장된 값이면
    if res[a][b][c]:
        return res[a][b][c]

    # 그외 조건
    if a < b < c:
        res[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
    else:
        res[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 res[a][b][c]

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

피보나치함수(#1003) 문제와 동일하게 풀면 되는데 문제 설명에 당황해 헤맸다.

 

 

[실행 결과]

 

[참고]

- https://jaimemin.tistory.com/619

- https://seraup.dev/8