C++ 알고리즘 - 9184 신나는 함수 실행 (동적 계획법 / 재귀)

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

 

#include <bits/stdc++.h>
#define endl "\n"

using namespace std;

/******** 전역변수 ********/
int arr[21][21][21];


/******** 함    수 ********/
int w(int a, int b, int c) {

	if (a <= 0 || b <= 0 || c <= 0) return arr[0][0][0];

	else if (a > 20 || b > 20 || c > 20) return w(20, 20, 20);

	// 저장된 값은 재귀 호출 및 계산하지 않고 바로 리턴
	else if (arr[a][b][c] != 0) return arr[a][b][c];

	// 리턴하지 않고 값 저장
	else if (a < b && b < c)
		arr[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);

	else
		arr[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 arr[a][b][c];
}


int main(void) {
	/******** C++ INIT ********/
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	/******** 지역변수 ********/
	int input1;
	int input2;
	int input3;


	/******** 구    현 ********/
	arr[0][0][0] = 1;

	while (true) {
		cin >> input1 >> input2 >> input3;
		if (input1 == -1 && input2 == -1 && input3 == -1) return 0;
		cout << "w(" << input1 << ", " << input2 << ", " << input3 << ") = " << w(input1, input2, input3) << endl;
	}
}