[BOJ/백준 9184][C++] 신나는 함수 실행

문제

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

백준 9184

백준 9184

 

문제 내용

문제에서 주어진 재귀 함수 의사 코드를 코드로 구현하면 되는 문제이다.

 

문제 풀이

문제에서 주어지는 코드를 보면, w(a, b, c)가 호출되는 수가 많다.

따라서, 재귀 문제이지만 dp(동적계획법)을 이용해서 문제를 풀어야 한다.

 

문제에서 주어진 재귀 코드 안의 조건을 위에서부터 1,2,3,4로 하자.

1번과 2번 조건은 그대로 재귀 함수로 구현하면 된다.

3번과 4번 조건은 재귀 함수가 많이 호출되기 때문에, dp를 사용해야 한다.

따라서 dp[a][b][c]의 값이 0이 아니라면 이미 계산이 된 것이기 때문에 값을 바로 return 하면 된다.

dp[a][b][c]의 값이 0이라면 3번과 4번의 방식으로 계산을 하게 된다.

 

dp를 사용하면 중복으로 값이 계산되는 상황을 줄일 수 있다.

(연산량을 줄일 수 있다.)

 

코드

#include <iostream>
using namespace std;

int dp[21][21][21] = { 0, };

int w_recur(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_recur(20, 20, 20);

	else if (dp[a][b][c] != 0) return dp[a][b][c];

	else if (a < b && b < c)
		dp[a][b][c] = w_recur(a, b, c - 1) + w_recur(a, b - 1, c - 1) - w_recur(a, b - 1, c);
	else
		dp[a][b][c] = w_recur(a-1, b, c) + w_recur(a-1, b - 1, c) + w_recur(a - 1, b , c-1) - w_recur(a-1, b - 1, c-1);

	return dp[a][b][c];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	//입력
	int a, b, c;

	//문제 해결
	while (true) {
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1) break;

		int result = w_recur(a,b,c);

		//결과 출력
		cout << "w(" << a << ", " << b << ", " << c << ") = " << result << '\n';
	}
}