동적계획법 - 백준 9184

백준 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)를 출력한다.

 

제한

 

• -50 ≤ a, b, c ≤ 50

 

접근.

점화식을 수도코드로 알려줘서 간단하게 캐시기능을 할 디피테이블만 사용하면 될 듯 싶었다.

허나 a,b,c가 -N 인 음수인 경우가 있어서 캐시를 3중 map 구조로 초기화하여 이용하기로 결정!

 

dp={}
for i in range(-50,51):
	dp[i]={}
	for j in range(-50,51):
		dp[i][j]={}
		for k in range(-50,51):
			dp[i][j][k]=51

def w_(a,b,c):
	if dp[a][b][c]!=51:
		return dp[a][b][c]
	if 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]=w_(20,20,20)
	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)
	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:
	N,M,K=map(int,input().split())
	if N==-1 and N==M and N==K:
		break
	print(f"w({N}, {M}, {K}) = {w_(N,M,K)}")

 

>> 문제는 맞혔으나 다른 이들의 풀이를 찾아본 결과 그냥 0~20까지의 캐시테이블만을 사용하는 것을 보고,

     점화식이 주어졌다고 대충보지 말자는 결론.

 

추가공부 - 사용가능 메모리가작으면서 음수까지 있을 때는 어떻게 풀것인가 고민해보기.