[백준] 9184 신나는 함수 실행

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

9184번: 신나는 함수 실행

 

dp 는 메모이제이션이 핵심이다.

특정 값이 들어갔을때마다 계산을 해주는 것이 아니라 이전에 계산했던 결과를 저장해놓고 그 값을 사용하는 것이 핵심!

이 문제에서는 인자가 3개이므로, 삼차원 배열로 각 인자들을 저장을 해주자.

 

[풀이]

1. 매번 호출할때마다, 그 결과값을 dp 배열에 저장해준다.

2. 함수를 호출했을때, 그 전에 그 함수로 호출한 적이 있다면 (dp[a][b][c] != 0) 이라면 dp[a][b][c] 값을 리턴해서 사용한다.

#include <iostream>
#include <cstring>
using namespace std;


long long dp[51][51][51];

long long w(int a, int b, int c) {

	if(a <= 0 || b <= 0 || c<=0)
		return 1;

	else if(dp[a][b][c] != 0) 
		return dp[a][b][c];

	else if(a>20 || b>20 || c> 20)
		return dp[20][20][20] = w(20, 20, 20);

	else if(a<b && b<c)
		return dp[a][b][c] = w(a, b, c-1) + w(a, b-1, c-1) - w(a, b-1, c);

	else
		return 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);

}

int main() {

	int a, b, c;
	while(true) {
		scanf("%d %d %d", &a, &b, &c);

		if(a==-1 && b==-1 && c==-1) break;

		memset(dp, 0, sizeof(dp));

		printf("w(%d, %d, %d) = %lld\n", a, b, c, w(a, b, c));
	}
}