글 읽기 - c++ 시간초과

gamy0315 3년 전 0

다른분들 코드를봐도 이런 재귀가 들어가는 듯한ㄴ데

왜 시간초과가 뜨는지 모르겠습니다.

#include <iostream>

int d[21][21][21];



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

int main() {
	std::cin.tie(NULL);
	std::cin.sync_with_stdio(false);
	std::ios_base::sync_with_stdio(false);

	d[0][0][0] = 1;
	d[20][20][20] = 1048576;
	while (true) {
		int a, b, c;
		std::cin >> a >> b >> c;

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

		std::cout << "w(" << a << ", " << b << ", " << c << ") = " << w(a, b, c) << "\n";
	}


	return 0;
}

djm03178 3년 전 1

보신 코드들은 메모이제이션이라는 기법을 사용하고 있는 것입니다. 여기서 선언하신 d 배열이 지금은 값을 저장하기만 할 뿐 실제로는 아무런 역할을 하지 못하고 있는데, 여기에 이전에 저장한 값이 있다면 계산을 다시 하지 않고 바로 반환하도록 해서 시간을 절약하는 기법입니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

c++ 시간초과

gamy0315 3년 전 0

djm03178 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말