[2193] 이친수

처음에 이진수 오타인줄 알았다. dp에 좀 더 익숙해 지기위해서 dp로 풀어보았다.

한번 틀렸던게 N으로 90이 들어오면 int범위를 넘어간다. dp문제를 풀때는 자료형도 주의해야겠다.

d[i][0]에는 i 번째 자릿수인 이친수의 끝자리가 0인 이친수,

d[i][1]에는 i 번째 자릿수인 이친수의 끝자리가 1인 이친수

를 저장했다.

i번째 자릿수인 이친수의 끝자리가 1이려면 i-1자릿수인 이친수의 끝자리가 0이어야 한다.

∴ d[i][1] = d[i-1][0]

i번째 자릿수인 이친수의 끝자리가 0이려면 i-1자릿수인 이친수의 끝자리는 0또는 1이어야 한다.

∴ d[i][0] = d[i-1][0] + d[i-1][1]

이 식을 1부터 N까지 돌리고

d[N][0]과 d[N][1]을 더하면 N번째 자릿수인 이친수의 갯수가 나온다.

---

#include <cstdio>

#include <queue>

using namespace std;

long long d[91][2];

int main(){

int N = 0;

scanf("%d",&N);

d[1][0] = 0;

d[1][1] = 1;

for(int i = 2;i<=N;i++){

d[i][0] = d[i-1][1] + d[i-1][0];

d[i][1] = d[i-1][0];

}

printf("%lld\n",d[N][0]+d[N][1]);

}