백준 9184번 C++

백준 9184번 신나는 함수 실행

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

9184번: 신나는 함수 실행

정답 코드

#include<iostream>
using namespace std;
int w(int a, int b, int c);
int dp[21][21][21];
int main() {
	while (1) {
		int a, b, c;
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1)
			break;
		int len = w(a, b, c);
		cout << "w(" << a << ", " << b << ", " << c << ") = " << len << "\n";
	}

}
int w(int a, int b, int c) {
	if (a <= 0 || b <= 0 || c <= 0)
		return 1;
	if (a > 20 || b > 20 || c > 20) {
		return w(20, 20, 20);
	}
	if (dp[a][b][c] != 0)
		return dp[a][b][c];
	if (a < b && b < c) {
		return dp[a][b][c] = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	}
	else {
		return dp[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);
	}
}

문제 풀이

재귀함수로만 풀면 시간초과가 발생하기 때문에
dp방식므로 풀었습니다. dp란 이미 체크한 곳은 계산
하지 않고 넘어가는 방식인데 피보나치, 타일 채우기 등
다양한 문제에서 사용됩니다. dp방식도 빠른 시일 안에 블로그에 업데이트하겠습니다!