이친수

• 해당 문제는 결과적으로 피보나치 점화식으로 풀리긴 한다.
  하지만, 이것은 해당 문제의 본질을 파악한 것은 아님

• key point! (본질을 파악한 풀이)
  1) 해당 자리수에서 끝이 0으로 끝나는 요소는 0과 1이 붙을 수 있다
  ex) 100 -> 101 / 100
  2) 해당 자리수에서 끝이 1로 끝나는 요소는 0만 붙을 수 있다
  ex) 101 -> 100

코드

#include <string>
#include <vector>
#include <iostream>
using namespace std;
// d[i][1] = i 자리수 일 때 끝이 1인 개수
// d[i][0] = i 자리수 일 때 끝이 0인 개수
long long d[92][2]; 
int N;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N;
    d[1][1] = 1; 
    d[2][0] = 1; 
    d[3][0] = 1; d[3][1] = 1;
    for(int i=4;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];
    return 0;
}

• 테이블 정의
  D[i][0] = i 자리수 2진수 중 0으로 끝나는 요소의 개수
D[i][1] = i 자리수 2진수 중 1으로 끝나는 요소의 개수

• 점화식
  D[i][0] = D[i-1][0] + D[i-1][1]
D[i][1] = D[i-1][0]

• 점화식 이해하기
  ex)
  i가 4일 경우 1000 / 1010 / 1001 이렇게 3가지 가 나오는데,
  끝이 0인 요소는 뒤에 0과 1을 추가할 수 있으며,
  끝이 1인 요소는 뒤에 0만 추가해야한다.
  즉, 1000 -> 10000 / 10001
     1010 -> 10100 / 10101
     1001 -> 10010 이 된다!
  결과적으로,
  D[5][0]은 D[4][0] + D[4][1]
  (끝이 0이 되는 것 = 전 자리수의 0요소 개수 + 전 자리수 1의 개수)
  D[5][1]은 D[4][0]
  (끝이 1이 되는 것 = 전 자리수의 0요소 개수)