백준 2193번: 이친구 C++코드(DP, 다이나믹 프로그래밍)

#include<iostream>

using namespace std;

long long arr[100] = {0,};

long long dp(int n){
    if(n < 3){
        return arr[n];
    }else{
        for(int i=3; i<=n; i++){
            arr[i] = arr[i-1] + arr[i-2];
        }
        return arr[n];
    }
}

int main(){
    int n;
    cin >> n;
    arr[1] = 1;
    arr[2] = 1;
    cout << dp(n);
}

설명

손으로 풀어가면서 점화식을 찾은거라 왜 이런지 정확한 원래는 모르겠으나, n자리라고 하면 n-1자리의 갯수와 n-2자리의 갯수를 더한 값이 n자리의 갯수이므로 이 점화식으로 풀었다. 그리고 n이 90까지가면 int의 범위를 넘겨버리므로, long long 을 사용하였다

 

문제점

범위 생각안하고 int로 잡은 점 때문에 한번 애를 먹었다.