3장 다이나믹 프로그래밍 - (3) 문제 풀이 1 [2193번 이친수]

/*

#include <iostream>

using namespace std;

int d[1001];

int f[1001];

int g[1001];

int main(void){

int n;

cin >> n;

g[0]=1;

g[1]=0;

d[1]=1;

for(int i=2;i<=n;i++){

f[i-1]=g[i-2];

d[i]=2*d[i-1]-f[i-1];

f[i]=g[i-1];

g[i]=d[i]-f[i];

}

cout << d[n] << endl;

return 0;

}

*/

#include <iostream>

using namespace std;

int main(void){

    int n;

    cin >> n;

    long long* d=new long long[n];

    d[0]=1;

    d[1]=1;

    for(int i=2;i<n;i++){

        d[i]=d[i-1]+d[i-2];

    }

    cout << d[n-1] << endl;

    return 0;

}

/*

#include <iostream>

using namespace std;

int d[91][2];

int main(void) {

int n; 

cin >> n;

d[1][0] = 0;

d[1][1] = 1;

for (int i = 2; i <= n; i++) {

d[i][0] = d[i - 1][0] + d[i - 1][1];

d[i][1] = d[i - 1][0];

}

cout << d[n][0] + d[n][1] << endl;

return 0;

}

*/