[백준] 알고리즘 9184번 - 신나는 함수 실행 문제

문제

소스코드

#include <bits/stdc++.h>
using namespace std;
int dp[51][51][51];
int w(int x, int y, int z) {
	if (x <= 0 || y <= 0 || z <= 0) //재귀 탈출조건
		return 1;
	if (dp[x][y][z] != 0) //이미 계산한 값이면
		return dp[x][y][z];
	if (x > 20 || y > 20 || z > 20) {
		dp[x][y][z] = w(20, 20, 20);
		return dp[x][y][z];
	}
	else if (x < y && y < z) {
		dp[x][y][z] = w(x, y, z - 1) + w(x, y - 1, z - 1) - w(x, y - 1, z);
		return dp[x][y][z];
	}
	else {
		dp[x][y][z] = w(x - 1, y, z) + w(x - 1, y - 1, z) + w(x - 1, y, z - 1) - w(x - 1, y - 1, z - 1);
		return dp[x][y][z];
	}

}
int main(){
   ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
   while (1) {
	   int a, b, c;
	   cin >> a >> b >> c;
	   if (a == -1 && b == -1 && c == -1) break;
	   if (a < 0 || b < 0 || c < 0) {
		   cout << "w(" << a << ", " << b << ", " << c << ") = "  << 1 << "\n";
		   continue;
	   }
	   cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a,b,c)<<"\n";
	    
   }
}

풀이

메모제이션 기법을 이용

문제에 나타나있는 조건대로 w함수를 작성

메모제이션 작성법

1. 재귀함수의 탈출문을 작성

2. 이미 방문한 dp면 즉 값이 초기화안된 값이 들어가져 있으면 이미 방문하였다는 거닌깐 그대로 사용