백준 2193. 이친수(DP)

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

2193번: 이친수

나는 문제 풀 때, 생각없이 직관적으로 푸는 습관이 있다. 구현문제처럼...

이 문제에 1<=n <=90이라는 조건이 없었으면, 나는 n이 가지는 이진수를 다 구하고, 앞자리 0인 이진수, 1연속인 이진수를 빼줬을 거같다. 다행히 문제에 조건이 있어서 이 방법을 시도하지 않았다. 

 

n=1, 2, 3일 때를 생각해보면 규칙을 발견할 수 있다. 

n = 2일 때의 이친수는 100 101이다. 

n = 3일 때의 이친수는 1000 1001 1010이다. 

n이 3일 때 나올 수 있는 이친수는 n이 2일 때 나올 수 있는 이친수의 맨 뒷자리가 0인 경우 2개, 맨 뒷자리가 1인 경우 1개 이다. 

따라서 점화식 d[i][0] = d[i-1][0] + d[i-1][1] (i 자리수의 이진수에서 맨뒷자리가 0인 경우), d[i][1] = d[i-1][0] (i 자리수의 이진수에서 맨뒷자리가 1인 경우)이다. 또한, i 번째 이친수의 개수는 d[i][0] + d[i][1]이다.

 

따라서 코드를 다음과 같이 작성한다. 

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <limits.h>
#include <algorithm>
using namespace std;

int n;
int arr[92];
long long d[92][2]; //i자리 이진수이고 끝자리가 j일때 이친수 개수/ 이진수 개수를 저장하므로 long long
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    d[1][0]=0;
    d[1][1]=1;
    d[2][0]=1;
    d[2][1]=0;

    for(int i = 3; 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];

    

}