[백준/C++] 9184 신나는 함수 실행 (S2)

유형	난이도	완료일	링크	특이사항
DP	실버2	23/02/07	https://www.acmicpc.net/problem/9184

<내 코드>

#include <iostream>
#include <cmath>

using namespace std;

int main(void)
{
	int a, b, c;
	
	while(true)
	{
		
		cin >> a >> b >>c;
		
		int origin_a = a;
		int origin_b = b;
		int origin_c = c;
		
		if( ( a == -1 && b == -1) && (c == -1))
			return 0;

		if((a<=0 || b<=0) || (c<=0))
		{
			cout << "w("<< origin_a <<", "<< origin_b <<", "<< origin_c << ") = " << 1<<"\\n";
			continue;
		}

		else if((a>20||b>20)||(c>20))
		{
			a=20, b=20, c=20;
		}

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

		arr[0][0][0] = 1;

		for(int i=0; i<21; i++) //하나라도 0이면 값은 1
		{
			for(int j=0; j<21; j++)
			{
				arr[0][i][j] = 1;
			}
		}

		for(int i=0; i<21; i++) //하나라도 0이면 값은 1
		{
			for(int j=0; j<21; j++)
			{
				arr[i][0][j] = 1;
			}
		}	

		for(int i=0; i<21; i++) //하나라도 0이면 값은 1
		{
			for(int j=0; j<21; j++)
			{
				arr[i][j][0] = 1;
			}
		}		

		for(int i=0; i<21; i++) //하나라도 0이면 값은 1
		{
			arr[0][0][i] = 1;
		}	
		for(int i=0; i<21; i++) //하나라도 0이면 값은 1
		{
			arr[i][0][0] = 1;
		}	
		for(int i=0; i<21; i++) //하나라도 0이면 값은 1
		{
			arr[0][i][0] = 1;
		}	

		for(int i=1; i<21; i++)
		{
			for(int j = 1; j<21; j++)
			{
				for(int k =1; k<21; k++)
				{
					if(i<j && j<k)
						arr[i][j][k] = arr[i][j][k-1] + arr[i][j-1][k-1] - arr[i][j-1][k];
					else
						arr[i][j][k] = arr[i-1][j][k] + arr[i-1][j-1][k] + arr[i-1][j][k-1] - arr[i-1][j-1][k-1];
				}
			}
		}

		cout << "w("<< origin_a <<", "<< origin_b <<", "<< origin_c << ") = " << arr[a][b][c]<<"\\n";		
	}

}

주어진 재귀함수가 수행하는 일을 동적 계획법을 이용해 더 빨리 해결하는 문제였다.

함수의 인자가 3개이지만 입력 가능한 수의 범위가 사실상 1~20으로 매우 작았기에 3차원 배열(arr[21][21][21])을 만들어 모든 값을 미리 채워두는 풀이를 생각했다.

가장 작은 단계(하나라도 0이 포함되면 1을 반환한다)의 값이 정해져 있으므로 인덱스에 0이 포함되는 경우에는 1을 저장해두고 이를 이용해 하나씩 다음 단계의 값을 구하게 하면 3차원 배열의 모든 부분을 채울 수 있다.

 

<다른 풀이>

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

굳이 내가 했던 것처럼 모든 값을 저장하고 시작하지 않아도 재귀 함수를 약간만 수정하는 것으로 답을 구할 수 있었다. 같은 계산을 반복하지 않게 해줌으로서 시간을 많이 단축시킬 수 있었다.

따라서 전역변수로 선언된 3차원 배열에 한 번 계산된 값들을 저장해두고(전역변수 → 메모리에 저장 : 메모이제이션(Memoization)) 필요할 때마다 가져와 사용하면 빠르게 답을 찾을 수 있다.