이친수_2193

2193 N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오. 이친수: 이진수중 다음의 두 조건을 만족하는 수. 이친수는 0으로 시작하지 않는다. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다. 그러므로 점화식을 세울 때 우리는 끝의 문자에 따라 d[n][1], d[n][0]으로 나누어 생각하여야 한다. 이친수는 0으로 시작하지 않으므로 초기값은 d[1][1] = 1, d[1][0] = 0 이다. 그렇다면 이 초기값을 기준으로, 나머지 점화식을 세울 수 있다. 여기서는 두번째 조건에 집중하면 된다. 1은 연속해서 사용할 수 없기 때문에 두번째 조건에 집중하면 점화식은 d[n][1] = d[n-1][0], d[n][0] ..