백준 2193번 C++

백준 2193번 이친수

https://www.acmicpc.net/problem/2193

2193번: 이친수

정답 코드

#include <iostream>
using namespace std;
long long int arr[91] = { 0,1,1 };
long long int fibo(int n) {
    if (n == 1 || n == 2)
        return 1;
    else if (arr[n] != 0)
        return arr[n];
    else {
        return arr[n] = fibo(n - 1) + fibo(n - 2);
    }

}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n;
    cin >> n;
    cout << fibo(n);
}

문제 풀이

dp를 활용해서 풀어야지 시간 초과가 나지 않는 문제입니다. 그리고 자료형의 범위가 크기 때문에 long long형을 사용해야 합니다. 1자리일때 1개(1), 2자리일때
1개(10), 3자리일때 2개(100,101), 4자리일때 3개(1000,1001,1010)식이여서 피보나치 수열과 형식이 똑같습니다. 그래서 피보나치 수열을 dp방식으로 구현해주면 문제를 해결할 수 있습니다.