문제 링크

문제 링크

💡문제를 보고 든 생각

단계별 문제풀이에서 동적계획법에 있는 문제였고 문제 안에서 "위의 함수를 구현하는 것은 매우 쉽다. 하지만, 그대로 구현하면 값을 구하는데 매우 오랜 시간이 걸린다."라는 구절 때문에 다이나믹 프로그래밍과 메모이제이션(Memoization)에 대해서 떠올렸습니다. 따라서 각 함수의 실행 결과를 자료 구조를 만들어서 저장하여 반복되는 연산 횟수를 줄이면 문제를 해결할 수 있다고 생각했습니다.

📝메모이제이션(Memoization)

한 번 계산한 결과를 메모리 공간에 메모하는 기법입니다. 캐싱(Caching)이라고도 합니다. 예를 들어 피보나치 함수와 같은 재귀 함수의 경우 f(0)이나 f(1)의 결과가 여러 번 사용됩니다. 이러한 함수의 값을 구할 때 매번 필요할 때마다 함수를 호출하는 것이 아닌 미리 변수에 저장해두었다가 꺼내어서 쓰면 비약적으로 수행 시간을 단축시킬 수 있습니다. 이 문제에서도 W(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)과 같은 경우 W(a-1,b,c)이 미리 저장되어있다면 W(a,b,c)를 더 빠르게 구할 수 있다.

🔨트러블 슈팅

메모이제이션을 적용할 메모리 공간을 어떠한 자료구조로 선언해야할 지에 대해 헷갈렸습니다. 값에 변화를 주어야 하고 순서가 고려되어야 하므로 리스트가 적절하다고 생각했습니다. 또한 a,b,c 각각의 값들에 따라 다른 메모리에 저장되어야 하므로 3차원 리스트를 이용하면 될 것이라고 생각했습니다. 다차원 배열을 이용하되 a,b,c의 값이 0이하일 때와 20 이상인 경우는 1과 W(20,20,20)으로 값이 고정되어 있으므로 메모이제이션의 범위를 0-20으로 설정했습니다. 파이썬으로 다차원 배열을 선언하는 것이 익숙하지 않아서 검색을 통해 찾아보았습니다.
다차원 배열 참고 블로그
해당 문제 풀이 참고 블로그

array = [[0 for _ in range(column)] for _ in range(row)] // 2차원 배열
array = [[[0 for _ in range(column)] for _ in range(row)] for _ in range(level)] // 3차원 배열

💻소스코드

import sys
sys.setrecursionlimit(10000)
input = sys.stdin.readline

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

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:
       return W(20,20,20)

   if dp[a][b][c]:
       return dp[a][b][c]
   elif a<b and b<c:
       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:
       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==-1 and b==-1 and c==-1:
       break
   answer = W(a, b, c)
   print("w(%d, %d, %d) = %d"%(a,b,c,answer))