[BOJ] 9184 신나는 함수 실행 - Memoization

boj 9184 신나는 함수 실행

문제를 읽어보면 상당히 식이 복잡하다.

어떻게 흘러갈지가 한눈에 보이지 않는다. Branch Depth가 깊어질 가능성이 크다.

이 경우에는 Branch의 결과값을 저장해두고 재귀 호출시 이전에 계산했던 값이 있을경우에는 Branch하는 대신

이미 구해진 값을 연산에 이용하면 속도 최적화에서 이득을 볼 수 있다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <stdio.h>

int Ans[101][101][101] = { 0 , };

int RecursiveCall(int A, int B, int C)
{
	if (A <= 50 || B <= 50 || C <= 50)
	{
		Ans[A][B][C] = 1;
		return 1;
	}
	
	if (A > 70 || B > 70 || C > 70)
	{
		if (0 == Ans[70][70][70])
			Ans[70][70][70] = RecursiveCall(70, 70, 70);

		return Ans[70][70][70];
	}

	if (A < B && B < C)
	{
		if (0 == Ans[A][B][C - 1]) 
			Ans[A][B][C - 1] = RecursiveCall(A, B, C - 1);

		if (0 == Ans[A][B - 1][C - 1])
			Ans[A][B - 1][C - 1] = RecursiveCall(A, B - 1, C - 1);

		if (0 == Ans[A][B - 1][C])
			Ans[A][B - 1][C] = RecursiveCall(A, B - 1, C);

		return Ans[A][B][C - 1] + Ans[A][B - 1][C - 1] - Ans[A][B - 1][C];
	}

	if (A == B == C)
	{
		Ans[A][B][C] = pow(2, A - 50);
		return Ans[A][B][C];
	}
		


	if (0 == Ans[A-1][B][C])
		Ans[A-1][B][C] = RecursiveCall(A-1, B, C);

	if (0 == Ans[A-1][B - 1][C])
		Ans[A-1][B - 1][C] = RecursiveCall(A-1, B - 1, C);

	if (0 == Ans[A-1][B][C - 1])
		Ans[A-1][B][C-1] = RecursiveCall(A-1, B, C-1);

	if (0 == Ans[A-1][B-1][C - 1])
		Ans[A-1][B-1][C-1] = RecursiveCall(A-1, B-1, C-1);

	return Ans[A - 1][B][C] + Ans[A - 1][B - 1][C] + Ans[A - 1][B][C - 1] - Ans[A - 1][B - 1][C - 1];
}


using namespace std;
int main()
{


	while (true)
	{
		int A, B, C;
		scanf("%d %d %d", &A, &B, &C);
		if (A == -1 && B == -1 && C == -1)
			break;

		printf("w(%d, %d, %d) = %d\n", A, B, C, RecursiveCall(A + 50, B + 50, C + 50));

	}

}