글 읽기 - c++ 시간초과

rkdgh3885 2년 전 0

시간초과가 나는 이유가 모르겠어요 ㅠㅠㅠ,,,

#include <iostream>
#include <stdio.h>
using namespace std;

int count_one;
int count_zero;

bool check[41] = { false, };
int memo_one[41] = { -1, };
int memo_zero[41] = { -1, };

void fibonacci(int n) {
	if (!check[n]) {
		if (n == 0)
			count_zero++;
		else if (n == 1)
			count_one++;
		else {
			fibonacci(n - 2);
			fibonacci(n - 1);
		}
	}
	else {
		count_zero += memo_zero[n];
		count_one += memo_one[n];
	}
}

int main() {

	int T, num;
	scanf_s("%d", &T);
	
	while (T != 0) {
		count_one = 0;
		count_zero = 0;
		
		scanf_s("%d", &num);
		fibonacci(num);
		check[num] = true;
		memo_zero[num] = count_zero;
		memo_one[num] = count_one;
		

		printf_s("%d %d\n", memo_zero[num], memo_one[num]);

		T--;
	}

	return 0;
}

djm03178 2년 전 0

memo라고 쓰셨는데 이게 메모이제이션을 염두에 두고 쓰신 거라면, 메모이제이션은 dp를 하는 과정에 있는 모든 상태에 대해 수행하면서 진행해야 합니다. 최종 결과에 대해서만 체크하려고 하면 처음부터 큰 수가 입력으로 들어왔을 때 그보다 작은 모든 수에 대해서는 상상을 초월할 정도로 많은 중복 호출이 일어나는 것을 그냥 지켜보고만 있게 됩니다.

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

문제

문제

출처

ICPC

c++ 시간초과

rkdgh3885 2년 전 0

djm03178 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말