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

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

9184번: 신나는 함수 실행 (acmicpc.net)

9184번: 신나는 함수 실행

조건들이 다 주어졌기 때문에 되게 쉽게 풀었다.

 

문제에 적힌대로 저대로만 사용하면 시간이 오래 걸리기 때문에 하나의 장치를 두어야 한다.

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다

---

추가해야 할 장치는 바로 메모이제이션(Memoization)이다.

 

메모이제이션은 재귀와 재귀를 사용하는 DFS, 동적 계획법과 같은 곳에서 많이 사용하는 방법으로, 이미 연산한 내용에 대해 중복 연산을 수행하지 않도록 도와주기 때문에 연산 속도를 향상시킬 수 있다.

 

이 메모이제이션을 적용하기 위해 (a, b, c)를 표시할 수 있는 3차 배열을 하나 정했고, 이외의 내용들은 조건에 해당하는 return 값을 주면서 재귀를 진행하면 문제를 풀 수 있다.

 

#include <iostream>

int store[21][21][21];

int solve(int a, int b, int c);

int main(void)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

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

		std::cout << "w(" << a << ", " << b << ", " << c << ") = " << solve(a, b, c) << '\n';
	}
}

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

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

	if (store[a][b][c])
		return store[a][b][c];

	if (a < b && b < c)
	{
		store[a][b][c] = solve(a, b, c - 1) + solve(a, b - 1, c - 1) - solve(a, b - 1, c);
		return store[a][b][c];
	}

	store[a][b][c] = solve(a - 1, b, c) + solve(a - 1, b - 1, c) + solve(a - 1, b, c - 1) - solve(a - 1, b - 1, c - 1);
	return store[a][b][c];
}