백준 알고리즘 9184번: 신나는 함수 실행 [C++]

문제 출처: www.acmicpc.net/problem/9184

9184번: 신나는 함수 실행

1. 코드

#include <iostream>

using namespace std;
int arr[21][21][21];

int w(int a, int b, int c)
{
	if (a <= 0 || b <= 0 || c <= 0)
		return 1;

	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)
{
	int a, b, c;
	while (1)
	{
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1) break;
		cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl;
	}
	return 0;
}

(실행)

2. 풀이

풀이 방법은 생각보다 어렵지않다.

int main(void)
{
	int a, b, c;
	while (1)
	{
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1) break;
		cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl;
	}
	return 0;
}

 

먼저 문제에서 요구하는 입력 조건과 출력 예시에 맞추어 코드를 작성한다.

int arr[21][21][21];

int w(int a, int b, int c)
{
	if (a <= 0 || b <= 0 || c <= 0)
		return 1;

	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];
}

재귀 함수에서 호출 시 입력된 수가 커지면 커질수록 연산 시간또한 커지게되는데 이때 동적 계획법을 이용하여 해결하면되는데 간단하게 설명하면 재귀 함수로 호출하여 나온 값을 임의의 배열이나 변수에 저장을 한 뒤 다시 같은 재귀 함수를 호출할 때 연산을 하는 것이 아닌 미리 저장된 값을 반환하는 방식이다.

그래서 배열 arr에 해당하는 값이 0이 아니라면 배열 arr에 위치한 값을 출력하고 그렇지않다면 연산을 한 뒤 값을 저장한 후 반환한다.

3. 느낀 점

동적 계획법에 대해 처음 알아보았는데 재귀 함수를 조금 빠르게 할 수 없나 생각은 하고 있었지만 그에 대한 해결책이 이미 있는 줄 몰랐다. 계속해서 노력해야겠다.