어떤 문제인가?

N번째 피보나치 수열의 값을 찾는 문제.

오버플로우

문제는 피보나치 함수는 뒤로 갈수록 값이 급격하게 늘어난다.
이러니까 C99에서 그나마 가장 큰 unsigned long으로도 값이 저장이 안된다.

그럼 어떻게 함??

2, 3, 5, 8, 13, 21이 있다고 하고 7로 나눈 나머지를 저장한다고 하자.
다 구하고 나눈다고 하자. 21%7 = 0이다.
그럼 하나하나씩 나머지를 구해 더한다 치자.
2, 3, 5, 1, 6, 0. 21%7과 결과값이 같다. 즉 구할때마다 나머지 연산을 취한 값이나 다 구해서 마지막으로 나머지 연산을 취한 값이 같다. 그래서 매 연산마다 나머지 연산을 해주면 그만이다.

기껏 피보나치 수열이라는 걸 알아놓고 오버플로우 때문에 3번이나 틀렸다. 그래도 다음에 풀 때 값진 경험이 되겠지.

다른 사람들의 풀이

int main(){
int f1=1,f2=2,f3,a;
scanf("%d",&a);
if(a<=2)f3=a==1?1:2;
for(int i=3;i<=a;i++){
f3=(f2+f1)%15746;
f1=f2%15746;
f2=f3;}
printf("%d",f3);}

aiden12191 님의 풀이
-> https://www.acmicpc.net/source/19701963

배열 따윈 사실 필요가 없다. 나도 그렇게 풀었고.