문제 링크

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

문제 설명

재귀 호출만 생각하면 신이 난다! 아닌가요?

다음과 같은 재귀함수 w(a, b, c)가 있다.

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)

위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다. (예를 들면, a=15, b=15, c=15)

a, b, c가 주어졌을 때, w(a, b, c)를 출력하는 프로그램을 작성하시오.

입력
입력은 세 정수 a, b, c로 이루어져 있으며, 한 줄에 하나씩 주어진다. 입력의 마지막은 -1 -1 -1로 나타내며, 세 정수가 모두 -1인 경우는 입력의 마지막을 제외하면 없다.

출력
입력으로 주어진 각각의 a, b, c에 대해서, w(a, b, c)를 출력한다.

문제 풀이

평범한 재귀 + dp를 추가하는 문제였다. 근데 틀렸다!

# 3차원 리스트 곱셈 선언
dp = [[[0] * 21] * 21] * 21

# 3차원 리스트 컴프리헨션 선언 
dp = [[[0 for _ in range(21)] for _ in range (21)] for _ in range (21)]

3차원 리스트 dp를 선언하는 중에 위와 같이 변경했더니 맞았다. 근데 정확한 차이가 뭘까? ......

곱셈으로 선언하게 되면 깊은 복사가 아닌 얕은 복사(shallow copy)가 되기 때문에 리스트 값이 계속 따라가게 되기 때문이었다...

곱셈 선언은 지양하고 컴프리헨션 방식으로 선언하쟈

맞은 코드

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

def w_def(a, b, c):
  if a <= 0 or b <= 0 or c <= 0:
    return 1
  elif a > 20 or b > 20 or c > 20:
    return w_def(20, 20, 20)

  if dp[a][b][c]:
    return dp[a][b][c]

  if a < b < c:
    dp[a][b][c] = w_def(a, b, c-1) + w_def(a, b-1, c-1) - w_def(a, b-1, c)
  else:
    dp[a][b][c] = w_def(a-1, b, c) + w_def(a-1, b-1, c) + w_def(a-1, b, c-1) - w_def(a-1, b-1, c-1)

  return dp[a][b][c]

while True:
  a, b, c = map(int, input().split())
  if a == -1 and b == -1 and c == -1:
    break

  result = w_def(a, b, c)
  print("w(" + str(a) + ", " + str(b) + ", " + str(c) + ") = " + str(result))