DP_백준_이친수_2193

이 문제 역시 마지막에 들어오는 숫자의 상태가 달라질 수 있다. 따라서 이 문제 역시 2차원 배열을 이용한다.

여기서 끝에 들어올 수 있는 숫자는 0 or 1밖에 없다. 시간 복잡도는 O(N)이다.

1. 정의 : dp[N][I] : N자리, 마지막 숫자 L(0 or 1)일때 이친수의 개수

2. 점화식 : dp[N][0] =  dp[N-1][0]+dp[N-1][1]

              dp[N][1] = dp[N-1][0]

3. 초기화 : dp[0][0]=0, dp[1][0]=0, dp[1][1]=1 

#include <iostream>
using namespace std;
 
int main() {
    int num;
    long long d[91][2];
 
    cin >> num;
    d[0][0] = 0;
    d[1][0] = 0;
    d[1][1] = 1;
    //Initialize
 
    for (int i = 2; i <= num; i++) {
        d[i][0] = d[i - 1][0] + d[i - 1][1];
        d[i][1] = d[i - 1][0];
    }
    //Calculate
 
    cout << d[num][0] + d[num][1] << endl;

이 문제에서 2차원 배열이 아닌 1차원 배열로 풀 수있다.

dp[N] : n자리 이친수의 개수

- 0으로 끝나는 경우

  앞에 0 or 1이 올 수있다.

  dp[N-1]

- 1로 끝나는 경우

  앞에 0만 올 수있다.

  dp[N-2]

dp[N] = dp[N-1] + dp[N-2]