Treejin's Note

문제 설명

• 정수 a, b, c가 주어진다.
• 재귀함수 w(a, b, c)는 위 사진의 회색영역과 같은 조건을 통해 작동하는 재귀함수이다.
• 최대한 짧은 시간이 걸리도록 재귀함수 w를 구현하라.

문제 풀이

이 문제는 재귀함수 w의 시간을 단축시키는 문제이다.

재귀함수의 시간을 단축시키려면 했던 연산을 다시 하지 않도록 해야한다.

그러려면 이미 했던 연산의 값을 저장해두면 된다.

즉, 메모이제이션을 이용하자!

우선 삼차원 배열을 이용해 a, b, c의 값에 따른 w함수의 결과값을 저장하도록 구현했다.

이 때, 문제에서 주어진 정수 a, b, c의 범위는 -50 이상 50 이하이다.

처음에는 이를 따라 무작정 삼차원 배열의 크기를 101 x 101 x 101 로 잡고 각 변수에 50씩을 더해서 값을 저장했다.

하지만 w함수 내부를 자세히 보면 a 또는 b 또는 c가 0보다 이하일 경우 1으로,

a 또는 b 또는 c가 20초과일 경우 w(20, 20, 20) 으로 값이 고정된다.

그러니 결국 연산 과정에서 a, b, c가 음수일 경우도, 20을 넘어갈 경우도 없다는 말이 된다.

그래서 삼차원 배열의 크기를 21 x 21 x 21 로 줄여 공간을 절약했다.

+ 문제 제출 후 통과를 했는데, 다른 사람들보다 400ms나 더 오래 걸리는 것을 발견했다!

아무리 코드를 비교해봐도 다른 부분이 없는데 하면서 살펴보던 도중... 출력 부분에서 endl을 "\n"으로 적용한 것을 발견했다.

알아보니 endl의 경우에는 flush함수(출력 버퍼에 있는 데이터를 지움)를 겸하기 때문에 "\n" 보다 속도가 느리다고 한다.

앞으로는 "\n"을 애용해야지 ㅎㅎ

Java를 쓰다가 C++로 넘어오니 모르는 것 투성이다😓

문제 풀이 코드

#include <iostream>

using namespace std;

int memory[21][21][21];

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 (memory[a][b][c])			// 이미 연산된 값일 경우
		return memory[a][b][c];		// 해당 연산 결과 반환
	if (a < b && b < c)
		return memory[a][b][c]  = w(a, b, c - 1) + w(a, b - 1, c - 1) - w(a, b - 1, c);
	
	return memory[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 main(int argc, char* argv[]) {
	int a, b, c;
	while (true) {
		cin >> a >> b >> c;
		if (a == -1 && b == -1 && c == -1)
			break;
		cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";	// 8ms
        	//cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << endl;	// 420ms
	}
	return 0;
}