[Python Algorithm] 신나는 함수 실행 BOJ #9184

문제

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

9184번: 신나는 함수 실행

 

내 문제 풀이

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

def w(a, b, c):
    if (a <= 0) | (b <= 0) | (c <= 0):
        return 1
    if (a > 20) | (b > 20) | (c > 20):
        return w(20, 20, 20)
    if memory[a][b][c]:
        return memory[a][b][c] # 이미 abc 값에 해당하는 memory 자리에 값이 할당되어 있다면(0이 아니라면), 연산 필요 없으므로 그대로 memory[a][b][c] 값을 리턴!
    if a < b < c:
        memory[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a,  b-1, c)
        return memory[a][b][c]
    memory[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 memory[a][b][c]

while True:
    n = list(map(lambda x: int(x), input().split()))
    if n == [-1, -1, -1]: break
    print(f"w({n[0]}, {n[1]}, {n[2]}) = {w(n[0], n[1], n[2])}")

👉 DP 문제로, 주어진 재귀함수를 메모이제이션을 활용하는 효율적인 함수로 바꿔주는게 포인트!

• 문제에서 주어진 함수를 거의 비슷하게 가져오고, 거기에 메모이제이션을 더해주었다.
• a, b, c가 a < b < c 조건과, else에 해당하는 조건의 연산을 수행하기 전에
  이미 memory[a][b][c]에 연산의 결과가 저장되어있다면, 굳이 중복된 연산을 할 필요가 없으므로
  그 뒤의 연산을 실행하지 않고 바로 memory[a][b][c]를 리턴하게 했다.
• 그리고 memory[a][b][c]에 그냥 0이 저장되어있고, 연산의 결과가 저장되어있지 않은 상태라면
  문제에서 주어진 각각의 연산을 실행하는 부분은 똑같이 구현하되, 다음에 중복된 연산을 피하기 위해서
  memory[a][b][c]의 자리에 해당하는 연산의 결과를 저장하도록 해주었다.

 

💡 피드백

• 처음엔 이게 무슨 문젠지,, 이해하는데 시간이 좀 걸렸는데,,
  비효율적으로 연산을 실행하는 함수를 DP 알고리즘을 통해 효율적으로 바꿀 수 있다는.,,?
  그런 부분을 보여주려는 의도가 담긴 문제인듯하다.