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

문제

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

9184번: 신나는 함수 실행

---

아이디어

재귀 호출로 실행하면 시간 초과가 발생한다. 이 경우는 DP를 이용해서 쉽게 해결할 수 있다. 

a, b, c 3개의 변수를 받기 때문에 3차원 배열을 생성한다. 

 

(a, b, c) 중 음수가 있는 경우 1을 반환하고, 모두 20보다 큰 경우 w(20, 20, 20)을 반환하도록 한다. 

이 때 재귀적으로 호출하면 w(20, 20, 20)를 구하기 위한 모든 과정을 반복해야 한다.

 

w(a, b, c)를 저장해놓고 배열에서 인덱싱을 통해 찾을 수 있으면 이런 과정을 불필요하게 반복하지 않을 수 있다. 

DP를 통해 함수 w()를 구현하는 과정은 다음과 같다.

 

1. 먼저 3차원 배열을 생성한다.

2. 만약 dp[ a ][ b ][ c ]가 0이 아니면(즉, 값이 입력되어 있으면) 그 값을 바로 출력한다.

3. 만약 만약 dp[ a ][ b ][ c ]가 0이면(즉, 값이 입력되어 있지 않으면) 문제에서 주어진 조건으로 탐색한다.

3-1. 이 경우는 a, b, c값이 점점 작아지면서 w(a, b, c)를 탐색한다. 어느 순간이 되면(a, b, c가 충분히 작아져서 배열에서 값을 찾을 수 있으면) dp[ a ][ b ][ c ]를 참조해서 w(a, b, c)를 return할 것이고 재귀적으로 업데이트 되면서 원하는 값을 구할 수 있다.  

---

Solution

import sys

dp = [[[0 for _ in range(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]
    
    else : 
        if a < b < c:
            dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, 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('w(' + str(a) + ', ' + str(b) + ', ' + str(c) + ') = ' + str(w(a, b, c)))