[Baekjoon] 9184번: 신나는 함수 실행

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

9184번: 신나는 함수 실행

 

---

 

문제 해결 과정

착안

구하고자 하는 값이 어떠한 점화식의 형태를 이용하여 구해지도록 함수를 구현해야 하므로, 동적계획법(dynamic programming)을 사용하여 구현해보고자 하였다.

 

구현

메모이제이션에 사용할 배열들을 편의상 전역 변수로 만들어 모든 함수에서 접근 가능하도록 구현하였다.

* int result[21][21][21] : 계산한 값을 저장.

* bool computed[21][21][21] : 계산 여부를 기록(저장된 값이 0인지 여부만으로 판단하지 못할 수 있어서 사용).

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

#include <iostream>

using namespace std;

int result[21][21][21] = { 0, };
bool computed[21][21][21] = { 0, };

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

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

	if (!computed[a][b][c])
	{
		computed[a][b][c] = true;

		if (a < b && b < c)
			result[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
		else
			result[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 result[a][b][c];
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int a, b, c;
	while (true)
	{
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1)
			break;

		cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
	}

	return 0;
}

 

실행 결과