https://www.acmicpc.net/problem/10826
10826번: 피보나치 수 4
피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다. 이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n>=2)가 ��
www.acmicpc.net
이 문제는 BOJ2407 조합 문제와 같이 피보나치 10000 의 자릿수가 2000 이 넘어가기 때문에 c++ 표준 자료형의 범위로는 표현할 수 없다. 마찬가지로 string 덧셈으로 풀 수 있는데, 이전 BOJ2407 번에서 구현한 string 덧셈이 비효율적이라 시간초과가 난다. 따라서 string 덧셈과정에서 역순으로 += 연산을 최대한 이용할 수 있도록 구현하여 시간제한 안에 풀 수 있도록 구현하였다.
새롭게 안 사실인데, 피보나치 4 문제의 질문 게시글 에서 문자열의 덧셈 방법 s = s + "string" 과 s += "string" 이 다르다는 것을 설명한다. 첫 번째 방법(s = s + "string") 은 string 을 새롭게 복사하기 때문에 O(s.size()^2) 의 시간이 걸린다고 한다. 두 번째 방법은 단순히 이어 붙이기 때문에, 시간적으로 매우 차이가 날 수 있다.
소스코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
|
#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
string s_add(string s1, string s2){
string ret = "";
int s1len = s1.length(), s2len = s2.length();
int is_carry = 0;
int i;
for(i = 0; i<s2len; i++){
char s = s1[i]-'0' + s2[i] + is_carry;
if(s > '9'){
is_carry = 1;
s -= 10;
} else {
is_carry = 0;
}
ret += s;
}
for(int j=i; j<s1len; j++){
char s = s1[j] + is_carry;
if(s > '9'){
is_carry = 1;
s -= 10;
} else {
is_carry = 0;
}
ret += s;
}
if(is_carry){
ret += "1";
}
return ret;
}
vector< string >v(10001);
int main(){
int n;
cin>>n;
for(int i=0; i<=10000; i++){
v[i] = "0";
}
v[2] = v[1] = "1";
for(int i=3; i<=10000;i++){
v[i] = s_add(v[i-1], v[i-2]);
}
reverse(v[n].begin(), v[n].end());
cout<< v[n] <<endl;
return 0;
}
|
cs |
'알고리즘 문제풀이' 카테고리의 다른 글
| BOJ 17472 다리만들기 2 (0) | 2020.11.24 |
|---|---|
| BOJ 1305 광고 (0) | 2020.09.24 |
| 1516 게임 개발 (0) | 2020.09.04 |
| BOJ 2407 조합 (0) | 2020.09.04 |
| LCS 최장 공통 부분 수열 (0) | 2020.09.03 |
