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

9184번 - 신나는 함수 실행

문제

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
    1

if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
    w(20, 20, 20)

if a < b and b < c, then w(a, b, c) returns:
    w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)

otherwise it returns:
    w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력

입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력

입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

제한

-50 ≤ a, b, c ≤ 50

예제 입력 1

예제 출력 1

w(1, 1, 1) = 2
w(2, 2, 2) = 4
w(10, 4, 6) = 523
w(50, 50, 50) = 1048576
w(-1, 7, 18) = 1

해결할 방법을 생각해보자.💡

문제에 나와있는 의사코드를 그대로 파이썬 코드로 짜주면 된다.

제한을 보면 a,b,c의 범위가 -50~50이지만 의사코드를 보면 20보다 클 때 결국 w(20, 20, 20)이 되므로 동적프로그래밍을 위한 리스트를 생성할 때 0이 20개가 있는 리스트를 20개를 가지고있는 리스트 20개를 만들어 주면 된다.

또, 주의해야할 점은 -1 -1 -1이 입력되었을 때 종료되게 for문이 아닌 while문을 사용해야한다는 점 정도이다.

코드 💻

import sys


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]:
        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]
    
    else:
        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 True:
    a,b,c = map(int, sys.stdin.readline().split())
    if (a == -1) and (b == -1) and (c == -1):
        break
    
    print(f'w({a}, {b}, {c}) = {w(a,b,c)}')

해결 로그

문제 푼 날짜	체크
2022-08-19	✔

2022 196
2021 22

맨 위로 이동 ↑