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

문제

---

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

9184번: 신나는 함수 실행

 

 

 

풀이

---

d = [[[10**9 for _ in range(101)] for _ in range(101)] for _ in range(101)]

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:
        if d[a][b][c] != 10**9:
            return d[a][b][c]
        else:
            d[a][b][c] = w(20,20,20)
            return d[a][b][c]
    elif a<b<c:
        if d[a][b][c] != 10**9:
            return d[a][b][c]
        else:
            d[a][b][c] = w(a,b,c-1) + w(a,b-1,c-1) - w(a,b-1,c)
            return d[a][b][c]
    else:
        if d[a][b][c] != 10**9:
            return d[a][b][c]
        else:
            d[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 d[a][b][c]

while True:
    a,b,c = map(int,input().split())
    if a==-1 and b==-1 and c==-1:
        break
    d[a][b][c] = w(a,b,c)
    print("w({0}, {1}, {2}) = {3}".format(a,b,c,d[a][b][c]))

 

 

함수의 규칙을 찾을려고했는데 못찾아서 그냥 문제에 있는 함수를 그대로 사용하였다.

대신, dp를 사용하였다.

d[a][b][c]에 w(a,b,c)의 값을 넣어 값이 한번 들어가있으면 재귀호출을 하지않고 d[a][b][c]를 사용하도록 하였다.

 

 

변수 a,b,c를 d[a][b][c] 이렇게 참조하기 위해서 d를 3차원으로 만들어주었다.

값이 이미 할당되었는지 판별하기 위해 초기값은 무한으로 주었다. 

d = [[[10**9 for _ in range(101)] for _ in range(101)] for _ in range(101)]

 

만약 a,b,c가 음수일경우에는 d[-50][-50][-50]이렇게 리스트의 뒤에서 부터 50번째에 있는 값을 참조한다.

 

w 함수는 문제의 함수와 비슷하게 만들어주었다. 

다른점은 만약 d[a][b][c]의 값이 있으면 d를 사용해주는 것이다. 

만약 d[a][b][c]가 무한이면 값이 할당되기 전이기때문에 w를 호출하고 무한이 아니면 값이 할당되었기 떄문에 d[a][b][c]를 반환한다.

 

import sys
input = sys.stdin.readline

dp = {}

def w(a, b, c):
   if (a, b, c) in dp.keys():
      return dp[(a, b, c)]
   else:
      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)
      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
   print(f'w({a}, {b}, {c}) = {w(a, b, c)}')

백준에서 들고온 코드이다.

딕셔너리로도 만들 수 있다. 그런데 a<b<c 문을 쓰지 않아도 돌아간다.. 왜지? 내 코드도 빼서 돌려봤는데 돌아간다..

왜그런지 아시는 분은 댓글로 알려주세요..