2193번 이친수

문제 출처 : https://www.acmicpc.net/problem/2193

 

2193번: 이친수

 

 

풀이 과정 

 

n= 1 -> 1 1개

n= 2 -> 10 1개

n= 3 -> 100, 101 2개

n= 4 -> 1000, 1001, 1010 3개

n= 5 -> 10000, 10001, 10010, 10100, 10101 5개 

 

예시를 통해 피보나치 수열이 나옴을 알 수 있었습니다.  피보나치 수열의 점화식은 다음과 같습니다.

 

Fn+2 = Fn+1 + Fn ( F0=0, F1=1 )

 

n이 90까지 나올 경우 피보나치 수열을 int로 계산할 경우 오버플로우가 발생하기 때문에 long long 타입을 사용했습니다.

 

 

소스 코드 

#include<iostream>
 
using namespace std;
 
int main() {
 
    int n; cin >> n;
    long long fib[91]; 
    fib[0] = 0 ;
    fib[1] = 1;
    for(int i=2; i<= n;i++) {
        fib[i] = fib[i-1]+ fib[i-2];
 
    }
    
    cout << fib[n];
}