[백준/DP/C++] 2193번 이친수

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

2193번: 이친수

두가지 방법으로 풀 수 있는 것 같다
다른 블로그들을 찾아보니 피보나치 수열로 많이 푼 것 같다

나는 다른 규칙을 찾아서
dp[n][s] : s로 끝나는 n자리 이친수 개수라고 정하고

dp[n][0] = dp[n-1][0] + dp[n-1][1]
dp[n][1] = dp[n-1][0]

라는 점화식을 가지고 코드를 짰다

#include <bits/stdc++.h>

using namespace std;
int n;
long long dp[91][2]={};

int main(void) {
    cin >> n;

    dp[1][0] = 0;
    dp[1][1] = 1;

    for(int i=2; i<=n; i++){
        dp[i][0] = dp[i-1][0] + dp[i-1][1];
        dp[i][1] = dp[i-1][0];
    }

    long long result = dp[n][0] + dp[n][1];
    cout << result << endl;

    return 0;
}

처음에는 dp배열과 result를 int형으로 잡고풀었더니 틀렸습니다가 나왔는데
피보나치 수열은 46항이 되면 int의 범위를 넘어간다고 한다

그래서 둘다 long long 형으로 바꿨더니 정답이 나왔다