[백준] 9184번 신나는 함수 실행 (Python)

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

9184번: 신나는 함수 실행

---

풀이과정

①문제 바라보기

굉장히 와닿지 않았다. 굉장히 굉장히.. 그래서 recursive로 먼저 코드를 작성해보았다.

그런데 문제의 설명대로 역시 15  15 15를 넣을 경우 굉장히 연산 속도가 느렸다.

조금 생각을 해보니 위의 코드는 탑다운 방식처럼 재귀를 사용해서 느린 것 같다. 그래서 반복문을 활용하는 보텀업 방식을 사용하면 해결 될 수 있을거라는 생각을 하게 되었다.

 

그런데 문제는, 값이 abc로 세 개기 때문에 쉽사리 점화식 작성이 안된다.. 딕셔너리를 활용할 지 생각해봤는데 그러면 점화식 작성이 굉장히 난해해진다. 

 

메모이제이션을 통해서 해결해야 한다는 점은 충분히 알 수 있었다. 그렇다면 그 값을 채워넣는게 문제인데 dp 테이블이 어차피 20까지니깐, 21까지  dp 테이블을 만들고, dp[a]][b][c] 값을 미리 저장해두면 쓸데없는 연산속도가 줄어든다.

대신, if dp[a][b][c]: return dp[a][b][c]를 해줘야! 이미 한 연산을 하지 않도록 해줄 수 있는 것이다.

 

②아이디어 열기

앞에서 말했던 메모이제이션을 활용하는 방법이다!

이를 활용하기 위해서는 두 가지가 필요했는데,

1. dp 테이블을 만들어야한다. (a,b,c)값을 넣어서 바로 찾을 수 있게끔!
2. 이미 연산된 값을 dp테이블에 저장할 수 있어야한다.

일단 dp테이블은, a,b,c>20이면 w(20,20,20)으로 return되기에 크기가 21x21x21이다.

그리고 연산된 값을 저장하기 위해서는 w함수 안을 손봐야하는데, if dp[a][b][c]: return dp[a][b][c]를 넣어줘야 이미 한 연산 값이 저장된다.

 

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]
    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]

dp = [[[0]*(21) for _ in range(21)] for _ in range(21)]

while True:
    a, b, c = map(int, input().split())
    if a == b == c == -1: break
    print(f'w({a}, {b}, {c}) = {w(a,b,c)}')