[백준/파이썬]9184 신나는 함수 실행

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

9184번: 신나는 함수 실행

 

qorwns 9184번

문제

문제는 단순하다.

 

재귀로 구현된 코드를 dp코드로 바꾸라는 거다.

 

dp 입문할 때 풀면 정말 좋은 문제인것 같다.

 

왜냐하면 이론으로 대충알던 dp를 어느 정도 감을 잡게 해준 문제라고 생각하기 때문이다.

 

정답

import sys

def w(a, b, c) :
    global dp_arr
    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 a < b and b < c :
        if dp_arr[a][b][c-1] != None :
            w1 = dp_arr[a][b][c-1]
        else :
            dp_arr[a][b][c-1] = w(a, b, c-1)    
            w1 = dp_arr[a][b][c-1]    
        if dp_arr[a][b-1][c-1] != None :
            w2 = dp_arr[a][b-1][c-1]
        else :
            dp_arr[a][b-1][c-1] = w(a, b-1, c-1)
            w2 = dp_arr[a][b-1][c-1]
        if dp_arr[a][b-1][c] != None:
            w3 = dp_arr[a][b-1][c]
        else :
            dp_arr[a][b-1][c] = w(a, b-1, c)
            w3 = dp_arr[a][b-1][c]
        return w1 + w2 - w3
    else :
        if dp_arr[a-1][b][c] != None :
            w1 = dp_arr[a-1][b][c]
        else :
            dp_arr[a-1][b][c] = w(a-1, b, c)
            w1 = dp_arr[a-1][b][c]
        if dp_arr[a-1][b-1][c] != None :
            w2 = dp_arr[a-1][b-1][c]
        else :
            dp_arr[a-1][b-1][c] = w(a-1, b-1, c)
            w2 = dp_arr[a-1][b-1][c]
        if dp_arr[a-1][b][c-1] != None :
            w3 = dp_arr[a-1][b][c-1]
        else :
            dp_arr[a-1][b][c-1] = w(a-1, b, c-1)
            w3 = dp_arr[a-1][b][c-1]
        if dp_arr[a-1][b-1][c-1] != None :
            w4 = dp_arr[a-1][b-1][c-1]
        else :
            dp_arr[a-1][b-1][c-1] = w(a-1, b-1, c-1)
            w4 = dp_arr[a-1][b-1][c-1]

        return w1 + w2 + w3 - w4


dp_arr = [[[None for i in range(21)] for j in range(21)] for k in range(21)]

while True :
    
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    
    if a == -1 and b == -1 and c == -1 :
        break

    print('w({}, {}, {}) = {}'.format(a, b, c, w(a, b, c)))

맞은 사람들 코드를 봤는데 나처럼 이렇게 무식하게 푼사람은 없는것 같다 ㅋㅋㅋ

 

솔직히 처음에 어떻게 풀지 막막했다.

 

처음 생각했던 방법은 재귀 코드를 보고 3중첩 for문으로 dp[21][21][21] 리스트의 모든 값을 저장하고 입력받은 값들을 뿌려주려고 했다.

 

근데 저 재귀 함수 코드만 보고는 할 수 없단 걸 깨닫게 되었다..

 

그래서 DP 이론에서 봤던 실행했던 함수는 다시 실행하지 않아도 된다! 라는 말이 기억이 나서 그대로 코드를 짜봤다.

 

이렇게 짜는게 Top Down방식인 메모이제이션 방식인것 같다.

 

처음에는 긴가민가하면서 짰는데 짜면서 이렇게 푸는 게 확실할 거라는 확신이 들었다.

 

이렇게 짜게 되면 입력값이 많으면 많을 수록 속도는 낮아지고 일정 dp_arr리스트가 다 채워지면 속도는 O(1)으로 일정해 질 것이다.

 

---

이번 문제를 풀면서 든 생각.

 

답지를 볼까 정말 고민 아주 많이 했는데 만약에 답지를 먼저 봤다면 이 문제 절대로 못 풀었을 것이다.

 

딱 보자마자 복잡해 보여서 풀 엄두도 못 냈을 듯. 근데 직접 생각하면서 풀면 규칙이 보이기 시작하면서 이해가 되는 것 같다.