글 읽기 - 피보나치4 시간초과 질문 드립니다.

kaskandk 5년 전 0

어느 부분이 시간초과가 나는지 모르겠습니다.

검색 후 비슷한 코드로 clear를 받았는데

어떤 부분이 문제가 있어서 제 코드는 시간초과가 발생하는건가요?

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <stack>
#include <functional>
#include <set>
#include <math.h>
#include <unordered_set>
#include <unordered_map>
#include <deque>
#include <cstdio>
#include <sstream>
#define ll long long int
#define ld long double
#define fr(i, a, b) for(int i = a; i < b; i++)
#define frb(i, a, b) for(int i = a; i >= b; i--)
#define sq(x) ((x) * (x))
#define PI ( acos(-1.0) )
#define pii pair<int,int>
#define mp make_pair
#define pb push_back
#define px first
#define py second
using namespace std;

int n;
void init() {
	cin >> n;
}

string dt[10001];

string add(string a, string b) {
	string res;
	int asz = a.length();
	int bsz = b.length();

	int buf = 0;
	int i;
	for (i = 0; i < bsz; i++) {
		char k = a[i] - '0' + b[i] + buf;
		buf = 0;
		if (k > '9') {
			buf = 1;
			k -= 10;
		}
		res = res + k;
	}

	fr(j, i, asz) {
		char k = a[j] + buf;
		buf = 0;
		if (k > '9') {
			buf = 1;
			k -= 10;
		}
		res = res + k;
	}
	if (buf) {
		res = res + '1';
	}

	return res;
}

void solve() {
	dt[0] = "0";
	dt[1] = "1";
	dt[2] = "1";

	int buf = 0;
	fr(i, 3, n+1) {
		dt[i] = add(dt[i - 1], dt[i - 2]);
	}

	frb(i, dt[n].size() - 1, 0) {
		cout << dt[n][i];
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	init();
	solve();
	//system("pause");
	return 0;
}

res = res + k; 와 res += k;는 서로 다릅니다. 전자는 res라는 문자열의 내용을 복사하고 그 뒤에 k라는 문자를 이어붙인 string 객체를 생성해서 res에 대입하는 것이고, 후자는 res의 기존 내용을 그대로 두고 뒤에 k라는 문자만 붙이는 것입니다. res = res + k; 라고 하면 이 문장이 실행될 때마다 기존의 res의 내용을 모조리 복사하는 작업이 들어가기 때문에 O(res.size()^2)의 시간이 소요됩니다.

51, 61, 64번째 줄을 모두 +=으로 고치니 252ms에 통과됩니다.

kaskandk 5년 전 0

djm03178님 정말 감사합니다.

몰랐던 사실을 알게되었습니다!

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

문제

문제

출처

ICPC

피보나치4 시간초과 질문 드립니다.

kaskandk 5년 전 0

djm03178 5년 전 2

kaskandk 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말