글 읽기 - 3038번 메모이제이션, 시간초과

q8514199 4년 전 0

안녕하세요.

제 질문은 두가지입니다.

1. 아래의 코드가 N이 증가함에 따라 시간이 오래걸리는데, dfs 함수에 소요되는 시간은 N과 관계없는 것아닌가요?

2. 그렇다면 preorder 함수에서 시간 초과가 일어난 것인가요>?

#include <iostream>
#include <math.h>
#include <memory.h>
using namespace std;
int tree[20][50000];
int n;
int dfs(int t,int n,int val) {
	if (t > 15) return 0;
	int& ret = tree[t][n];
	if (ret != -1) return ret;
	ret = val;
	if ((int)log2(n) == t) {
		if (t % 2 == 0) {
			dfs(t + 1, pow(2, t) + n, 2 * val);
			dfs(t + 1, 2 * pow(2, t) + n, 2 * val + 1);
		}
		else {
			dfs(t + 1, pow(2, t) + n, 2 * val+1);
			dfs(t + 1, 2 * pow(2, t) + n, 2 * val);
		}
	}
	dfs(t + 1, n, val);	
}

void preorder(int a) {
	if (tree[n-1][a] == -1) return;
	cout <<tree[n-1][a]<<" ";
	preorder(2 * a);
	preorder(2 * a + 1);
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n;
	memset(tree, -1, sizeof(tree));
	dfs(1, 1, 1);
	dfs(1, 2, 2);
	dfs(1, 3, 3);

	preorder(1);
}

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

문제

문제

출처

ICPC

3038번 메모이제이션, 시간초과

q8514199 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말