[백준 9184] 신나는 함수 실행

문제에서 대놓고 점화식을 줬다. 천사같은 문제라고 볼 수 있다.

고민해야될 것은 Top-Down으로 할 지, Bottom-Up으로 할 지이다.

 

그냥 둘 다 해보자.

 

1. Top-Down문제에서 대놓고 그대로 구현하면 값을 구하는데 오래 걸린다고 한다.DP 1번 문제였던 피보나치와 마찬가지로 너무 많은 재귀함수가 호출되기 때문이다.그러면.. 해결방법은 재귀함수 호출을 줄이면 된다. 뭘 이용해서 ? Memorization !

 

이 문제에선 배열에 저장된 값이 0이 될 수 있기 때문에, 처음에 배열에 모든 값을 -1로 초기화해주자.

 

왜 ?

 

예를 들어, w[20][20][20]을 구하기 위해서 w[20][20][19]에 접근했더니 w[20][20][19]에 저장된 값이 0이라고 가정해보자.

재귀함수를 통해 이미 계산된 값이라면 더 돌아볼 것도 없이 0을 리턴해주면 되지만, 초기화된 값이었다면 w[20][20][19] 값을 구하기 위해 또 다른 재귀함수가 실행될 것이다.

자... 이 저장된 0은 재귀함수를 통해 이미 계산된 값인지 프로그램 실행 때 초기화된 값인지.. 어떻게 알 것인가 ? 모른다;; 그렇기 때문에, 아직 계산되지 않은 원소라는 의미에서 배열 안에 모든 원소를 -1로 초기화시켜주자.

 

이제 재귀함수만 작성하면 끝난다.재귀함수 내에서 w[a][b][c]에 저장된 값이 -1인지 체크해보자. -1이라면 문제에서 준 점화식을 통해 값을 계산하면 될 것이고, -1 아니라면 이미 계산된 값이기 때문에 그 값을 바로 리턴하자.

 

그럼 끝! 이 아니다. a, b, c 중 하나라도 0보다 작거나 같은 경우와 20보다 큰 경우는 따로 처리해주어야하기 때문에, w[a][b][c]에 먼저 접근하지 말고 a, b, c의 값을 먼저 체크 해주어야 한다. 

 

무슨 소리인지 모르겠다면 코드로 한번 보자.

#include <bits/stdc++.h>
using namespace std;

int w[21][21][21];

int getW(int a, int b, int c) {
	// a, b, c 범위 체크
	if (a <= 0 || b <= 0 || c <= 0) return 1;
	if (a > 20 || b > 20 || c > 20) return getW(20, 20, 20);
	
	// 이미 계산된 a b c인지 확인
	// 계산된 게 맞다면 바로 저장된 값 리턴
	if (w[a][b][c] != -1) return w[a][b][c];
    
	// 아니라면 점화식 수행
	if (a < b && b < c) return w[a][b][c] = getW(a, b, c - 1) + getW(a, b - 1, c - 1) - getW(a, b - 1, c);
	else return w[a][b][c] = getW(a - 1, b, c) + getW(a - 1, b - 1, c) + getW(a - 1, b, c - 1) - getW(a - 1, b - 1, c - 1);

	return -1;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	// 배열 안에 모든 값 -1로 초기화, for문을 사용하는 것보다 빠름
	memset(w, -1, sizeof(w));

	int a, b, c;
	while (true) {
		cin >> a >> b >> c;

		if (a == -1 && b == -1 && c == -1) break;

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

	return 0;
}

---

2. Bottom-Up

점화식이 있을 때 Bottom-Up방식 구현은 너무나도 쉽다.그냥 for문을 통해 구현해서 배열w를 채우자 !

#include <bits/stdc++.h>
using namespace std;

int w[21][21][21];

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
    
	for (int a = 0; a < 21; a++)
		for (int b = 0; b < 21; b++)
			for (int c = 0; c < 21; c++) {
				// a, b, c가 20을 넘는 경우는 없기 때문에, 0보다 작거나 같은 경우만 신경쓰자.
				if (a <= 0 || b <= 0 || c <= 0){
					w[a][b][c] = 1;
				}
				else if (a < b && b < c){
					w[a][b][c] = w[a][b][c - 1] + w[a][b - 1][c - 1] - w[a][b - 1][c];
				}
				else {
					w[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];
				}
			}
				

	int a, b, c, result;
	while (true) {
		cin >> a >> b >> c;

		if (a == -1 && b == -1 && c == -1) break;

		if (a <= 0 || b <= 0 || c <= 0) result = 1;
		else if (a > 20 || b > 20 || c > 20) result = w[20][20][20];
		else result = w[a][b][c];

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

	return 0;
}