이친수

pinary[i] = i 자리 이친수를 만들 수 있는 경우의 수

pinary[i]는 i-1 자리 이친수 패턴을 그대로 적용할 수 있다.

그리고 위 사진을 잘 보면 i 자리 이친수는 i-2 자리 이친수 패턴이 적용된 i -1 자리 이친수에 2가지 경우 (0, 1)가 가능하다.

 

예를 들어서 i = 5 라고 하면,

10000, 10001

10101, 10100

빨간색으로 칠한 부분이 i = 3 자리인 이친수이다.

pinary[i] 는 pinary[i-1]의 경우의 수를 그대로 가져가고, 추가로 pinary[i-2]의 경우의 수가 추가된다.

 

결국 pinary[i] = pinary[i-1] + pinary[i-2] 가 성립