[백준/실버2] 9184번 신나는 함수 실행 | DP | 파이썬 Python

문제

https://www.acmicpc.net/problem/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)를 출력한다.

 

예제

 

나의 풀이

• 정수가 3개인 데다가 a, b, c가 각각 값이 다른 값을 가질 수 있기 때문에 DP를 이용한다면 어떤 식으로 이전 값을 저장해야 할지 로직이 생각나지 않았다.

 

다른 사람의 풀이

import sys
input = sys.stdin.readline

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
    
    elif a > 20 or b > 20 or c > 20:
        return w(20, 20, 20)

    elif dp[a][b][c]:
        return dp[a][b][c]
    
    elif 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, input().split())

    if a == b == c == -1:
        break
    else:
        result = w(a,b,c)
        print(f'w({a}, {b}, {c}) = {result}')

• 3차원 배열을 생성해서 `w(a, b, c)`의 값을 저장한다.
  • 두 번째 조건으로 인해 `a, b, c`의 최대값이 `20`을 넘어가지 않기 때문에 리스트의 길이는 `21`로 설정한다.
• 이미 `dp[a][b][c]` 값이 존재한다면 그 값을 출력하고, 아니면 새로 값을 계산해서 `dp[a][b][c]`에 할당한다.

 

회고

• 막상 풀이를 보니까 간단하게 풀 수 있는 문제였다.
• 잠시 a, b, c 조합마다 값을 저장하면 어떨까? 떠올리긴 했지만 구체적인 구현으로 이어지진 않았다.
• 에이 이건 아니겠지? 하고 넘어간 방법이 정답이었을 때가 꽤 있었다.
• 어차피 실전이 아니기 때문에 생각나는 방법은 다 시도해보는 것도 괜찮을 거 같다. 실패에서도 배울 점이 있을 테니까!