글 읽기 - 시간초과에 원인을 모르겠습니다.

jaeung95 4년 전 0

ret를 이용해 참조해서 접근하면 시간초과가 안나는데

ret를 사용하지 않고 풀면 시간초과가 나는데

이유가 궁금합니다..

참조 하냐 안하냐에 따라 왜 시간이 달라지는지 궁금합니다

int dp(int n);
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	clock_t begin, end;
	begin = clock();
	int n;
	cin >> n;
	cout << dp(n);
	end = clock();
	cout << "수행시간 : " << ((end - begin) / CLOCKS_PER_SEC) << endl;
}
int dp(int n) {
	if (n == 1)return 1;
	if (n == 2)return 3;
	int &ret = result[n];
    //ret부분!
	if (result[n] != 0)return result[n];
	return ret = (dp(n - 1) + 2 * dp(n - 2)) % 10007;
}

sait2000 4년 전 0

통과한 코드 말고 시간초과가 난 코드를 제출한 그대로 올려주세요

이유는 아마 result[n]이 안 바뀌어서일 것 같기는 한데, 실제 코드를 보기 전에는 모릅니다.

jaeung95 4년 전 0

다시 올렸어요

이런식으로 제출되면 시간초과 되네요

int dp(int n);
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	clock_t begin, end;
	begin = clock();
	int n;
	cin >> n;
	cout << dp(n);
	end = clock();
	cout << "수행시간 : " << ((end - begin) / CLOCKS_PER_SEC) << endl;
}
int dp(int n) {
	if (n == 1)return 1;
	if (n == 2)return 3;
	if (result[n] != 0)return result[n];
	return result[n] = (dp(n - 1) + 2 * dp(n - 2)) % 10007;
}

sait2000 4년 전 0

일단 지금 코드는 백준에서는 컴파일 에러가 발생합니다 헤더를 include하지도 않고 result가 선언되지도 않았으니까요.

jaeung95 4년 전 0

질문좀 바꿀께요! 시간을 따로 측정했는데

밑에 코드로 시간측정해본거랑

주석에 해당하는 코드로 시간측정하는거랑 2배차이 나는데

이유가 뭘까요?

#include <iostream>
#include <algorithm>
using namespace std;
int result[1001];
int dp(int n);
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);t n;
	cin >> n;
	cout << dp(n);
}
int dp(int n) {
	if (n == 1)return 1;
	if (n == 2)return 3;
	if (result[n] != 0)return result[n];
	//result[n] = (dp(n - 1) + 2 * dp(n - 2)) % 10007;
    //return result[n];
	return result[n] = (dp(n - 1) + 2 * dp(n - 2)) % 10007;
}

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

문제

문제

출처

ICPC

시간초과에 원인을 모르겠습니다.

jaeung95 4년 전 0

sait2000 4년 전 0

jaeung95 4년 전 0

sait2000 4년 전 0

jaeung95 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말