문제

풀이

함수에 대한 이해

w(a,b,c)라는 함수인데
세가지 정수형 a, b, c을 매개변수로 입력받고, 정수형으로 return

1. #a 또는 b 또는 c가 0보다 작거나 같을 때 1을 리턴
   if (a <= 0 or b <= 0 or c <= 0)
   return 1

2. #a 또는 b 또는 c가 20보다 클 때 w(20, 20, 20)을 리턴

3. #a < b < c를 만족할 때
   w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c)를 리턴

4.나머지는
w(a-1, b, c) + w(a-1, b-1, c) + w(a-1, b, c-1) - w(a-1, b-1, c-1)

이문제에 time limit은 1초이고
최대 연산횟수인 w(50, 50, 50)을 고려했을 때 그 값이 1048576 인걸 보아
재귀가 매우 많이 일어나는 것을 알 수 있고 따라서 다른 방식으로 문제를 해결해야 한다.

dp를 적용해보자면 먼저
이 함수들을 재귀하면서 dp테이블에 등록되있으면 (이전에 계산해봤던 놈이면) 재귀를 하지말고저장되어 있던 놈을 dp테이블에서 바로 꺼내준다
일단 dp테이블이 3차원 리스트가 되어야하고 그렇다면 dp 테이블 크기는 20 X 20 X 20이
된다.

메모이제이션을 이용해서 풀어봤다.

코드

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(dp[20][20][20] == 0):
      dp[20][20][20] = w(20, 20, 20)
      return dp[20][20][20]
    else:
      return dp[20][20][20]
  elif (a < b and b < c):
    if(dp[a][b][c] == 0):
      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]
    else:
      return dp[a][b][c]
  else:
    if(dp[a][b][c] == 0):
      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]
    else:
      return dp[a][b][c]
      
import sys

a = 0
b = 0
c = 0


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

while True:
  a, b, c = map(int, sys.stdin.readline().split())

  if (a == -1 and b == -1 and c == -1):
    break;
  else:
    print('w({}, {}, {}) ='.format(a, b, c), w(a,b,c))