[BOJ / 파이썬] 9184: 신나는 함수 실행

백준 / BOJ / Python / 파이썬

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

9184번: 신나는 함수 실행

단계 : 동적 계획법 1

알고리즘 분류 : 다이나믹 프로그래밍, 재귀

 

풀이:

w라는 재귀 함수의 실행에 있어서 여러번의 테스트를 거칠 때 더 빠르게 돌아가도록 하는 문제이다.

 

어차피 구해야 하는 값을 한번은 구해야하기에 해당 값을 저장할 dict라는 딕셔너리를 하나 전역변수로 만들어준다. 그리고 문제에 나와있는 w 함수를 그대로 구현하는 대신 현재 a, b, c 값에 대해 이미 dict에 구해진 값이 있다면 w 함수에서 나오게 진행하였다.

 

입력은 -1이 될 때 끝나므로 a, b, c 값이 다 -1일 때 무한 루프에서 탈출 할 수 있게 하였으며 그 외에는 dict에 값이 있다면 바로 답을 내고 없다면 w 함수로 들어가도록 실행하였다.

 

예전에 짠 코드라 a == b == c == -1 등 조금 더 깔끔하게 처리할 수 있는 부분들이 이제와서 많이 보여 그렇게까진 마음에 들지 않지만 시간 내에 통과했으니 굳이 다시 깔끔하게 고치진 았겠다. 딕셔너리로 하지 않고 3차원 배열을 사용해도 된다.

 

코드

def w(a, b, c):
    global dict
    if (a, b, c) in dict.keys():
        return dict[(a, b, c)]
    if a <= 0 or b <= 0 or c <= 0:
        return 1
    if a > 20 or b > 20 or c > 20:
        dict[(a, b, c)] = w(20, 20, 20)
        return dict[(a, b, c)]
    if a < b and b < c:
        dict[(a, b, c)] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c)
        return dict[(a, b, c)]
    else:
        dict[(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 dict[(a, b, c)]


dict = {}
while True:
    a, b, c = map(int, input().split())
    if a == b and a == c and b == -1:
        break
    if (a, b, c) in dict.keys():
        temp = dict[(a, b, c)]
    else:
        temp = w(a, b, c)
    print(f"w({a}, {b}, {c}) = {temp}")