이번 문제는 결과값의 패턴을 파악하여 해결하는 문제였다. 본인이 파악한 결과값의 패턴은 다음과 같다.

• n이 1일 때와 2일 때, 모두 결과값이 1이다.
• n이 3일 때는 결과값이 2이다.
• n이 4일 때는 결과값이 3이다.
• n이 5일 때는 결과값이 5이다.
• n이 6일 때는 결과값이 8이다.
• n이 7일 때는 결과값이 13이다.

이 결과값들을 자세히 보면 result[n] = result[n-2] + result[n-1] 이라는 것을 알 수 있다. 패턴을 파악하고 나면 문제를 해결하는 것은 매우 간단하다.

Code

#include <iostream>
#define MAX 91
using namespace std;

int n;
long long result[MAX];

void Input(){
    cin>>n;
}

void Solution(){
    result[1]=1;
    result[2]=1;
    for(int i=3; i<=n; i++){
        result[i]=result[i-2]+result[i-1];
    }
    cout<<result[n]<<endl;
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    Input();
    Solution();
    return 0;
}