[백준 알고리즘] - 신나는 함수 실행 (9184번) with Python

📎 간략한 문제 정리

• 주어진 재귀 함수가 속도 이슈 없이 작동하도록 만듭니다.

  if a <= 0 or b <= 0 or c <= 0, then w(a, b, c) returns:
      1
  
  if a > 20 or b > 20 or c > 20, then w(a, b, c) returns:
      w(20, 20, 20)
  
  if a < b and b < c, then w(a, b, c) returns:
      w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)
  
  otherwise it returns:
      w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

📈 문제 분석

• 전형적인 DP 문제인 피보나치와 유사한 형식입니다. 단순 반복이 아니라 결과를 저장하면서 꺼내오는 구조로 작성해야 합니다.

🙋‍♂️ 내가 처음 생각한 해결 방법

• pseudo code에 나온 그대로 구현하지만 결과를 저장할 수 있는 dp를 구현합니다. 우선 dp에 결과가 있는지 확인한 후 없을 때에만 연산하고 저장합니다.

💻 풀이한 코드

from sys import stdin
input = stdin.readline
dp = {}
def recursive_w(a, b, c):
    if (a, b, c) in dp:
        return dp[(a, b, c)]
    elif a <= 0 or b <= 0 or c <= 0:
        dp[(a, b, c)] = 1
    elif a > 20 or b > 20 or c > 20:
        dp[(a, b, c)] = recursive_w(20, 20, 20)
    elif a < b and b < c:
        dp[(a, b, c)] = recursive_w(a, b, c-1) + recursive_w(a, b-1, c-1) - recursive_w(a, b-1, c)
    else:
        dp[(a, b, c)] = recursive_w(a-1, b, c) + recursive_w(a-1, b-1, c) + recursive_w(a-1, b, c-1) - recursive_w(a-1, b-1, c-1)
    return dp[(a, b, c)]
while True:
    x, y, z = map(int, input().split())
    if x == -1 and y == -1 and z == -1:
        break
    print(f"w({x}, {y}, {z}) = {recursive_w(x, y, z)}")

📝 해결 과정에서 만난 문제, 고민들

• dp[(a, b, c)]에 값을 넣을 때 오른쪽의 연산을 한 후 결과를 넣어야하나 잠시 고민했습니다. value에 연산 결과인 리터럴 값을 넣어주고 싶은데 혹시나 식 자체가 들어가는 경우가 있을지 생각해보았습니다. 파이썬에서 메소드가 일급 객체여서 value에 메소드 자체가 들어갈 수 있다는 가능성을 생각해보았고, 아래와 같은 테스트를 진행했습니다.

  dict = {}
  def test():
      pass
  dict["a"] = test()
  print(dict)
  
  # 결과
  # {'a': None}

  test 메소드가 나오는 것을 생각해보았는데 None이 나오는 것을 보고 메소드의 리턴값을 value로 가진다고 생각했습니다. 테스트로 리턴값을 갖는 메소드를 작성해보았습니다.

  dict = {}
  def test():
      return 10
  dict["a"] = test()
  print(dict)
  
  # 결과
  # {'a': 10}

  예상대로 return 값이 value로 저장되었습니다. 그래서 최종 코드는 오른쪽 연산이 먼저 진행되고 그 결과물이 왼쪽 변수에 담기므로 temp 변수 없이 직접 넣는 코드를 구현했습니다.

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