프로그래머스 : 타일 장식물

피보나치 수열 

 

점화식 

Sn = Sn-1 + pn;

 

#include <string>
#include <vector>

using namespace std;
/* n1 = 4*1;
n2 = n1 +2*1;
n3 = n2 + 2*2
n4 = n3 + 2*3
n5 = n4+2*5
*/

long long p[81];
long long s[81];
long long solution(int N) {
    p[1] = 1; 
    s[1] = 4;
    p[2] = 1;
    s[2] = 6;
    for(int i=3; i<=N; i++){
        p[i] = p[i-1] + p[i-2];
        s[i] = s[i-1] + 2*p[i];
    }    

    return s[N];
}