백준 2193번 - 이친수

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

문제의 조건을 보면서 눈에 띄는 것은 1이 두 번 연속으로 나타나지 않고 처음에 0으로 시작하지 않는 것이다. 

해당 문제를 보면서 90이라는 N의 범위를 보고 모든 경우를 구할 경우 최악의 경우 (2^90) 이기 때문에 다른 방법을 생각해야 한다.

여러가지 해결 방법이 있겠지만 n일 때 이전에 구한 값에서 그 값을 갖고오는 방법이다.
2차원 배열로 생각하였고 변수가 dp[2][n]일 경우에
dp[0][n] = n번째에서 그 값이 0인 경우,
dp[1][n] = n번째에서 그 값이 1인 경우로 나누었다.

그리고 각각 그 값이 0 일 경우에는 이전 n-1이 0과 1일 때 모두 가능하고 1일 경우에는 이전 n-1이 0일때만 가능하다.


그리고 가장 중요한 것은, 

항상 풀때마다 이 부분을 틀리는 데 n의 범위가 90 이면 int형으로 제대로 된 값을 구할 수 없어서 long 타입으로 제출해야 올바른 값이 나오게 된다.

#include <iostream>
#include <vector>
using namespace std;
 
int main(){
    int n;
    cin>>n;
    
    vector<vector<long>> dp(n+1,vector<long> (2,0));
    
    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];
    }
    
    cout<<dp[n][0]+dp[n][1]<<endl;
    return 0;
}