백준 2193 - 이친수

조건)

1. 첫번째 자리에는 0 올 수 없음

2. 1 연속으로 올 수 없음

 

테이블

d[i] - i 자리 이찬수의 갯수

d[1] - 1 // 0으로 시작 못하니깐 1만 가능

d[2] - 1 // 1 연속해서 못오니깐 1 0 만 가능

d[3] - 2개
1 0 0
1 0 1 

그런데 어떻게 보면 
d[2]   d[3]
1 0   + 0
      + 1
이렇게 앞의 값과 연관성이 있다는 걸 알 수 있는데
만약에 앞의 수가 0으로 끝난다면 +0,+1이 두개 다 올 수 있지만
1로 끝나는 수의 경우에는 +0만 올 수 있음

그렇다면 0으로 끝나는 수의 갯수 / 1로 끝나는 수의 갯수를 따로 생각해서 d[i]의 기준에서 생각해보면
d[i][0] = i-1자리 이찬수에서 0으로 끝나는 수 + i-1자리 이찬수에서 1로 끝나는 수
d[i][1] = i-1자리 이찬수에서 0으로 끝나는 수

이렇게 계산하면 숫자가 무한정 커지기 때문에 값 하나하나를 BigInt 자료형으로 저장해서 출력만 String()으로 변환해주면 완료