백준 2193 : 이친수

우선 위의 문제의 규칙대로 1의 자릿수(N) 부터 적어보자.

N =1 일 때

1

N =2 일 때

10

N= 3 일 때

100, 101

N= 4 일 때

1001, 1000, 1010

N= 5 일 때

10010, 10000 , 10100, 10101

 

N이 3일 때, 마지막 수가 0이 되려면, 그 전의 숫자가 1이거나 0이어야 한다.

혹은 1이 되려면, 0이어야 한다. 그 전의 수에 의해서 값이 정해지는 것이다!

i가 해당 자릿수, 끝나는 숫자가 j인 2차원 배열을 정의해보자.

 

마지막 자릿수(j)가 0일 때,

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

마지막 자릿수가 1일 때,

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

라는 점화식이 성립함을 알 수 있다!

 

N = int(input())

d = [[0]*2 for i in range(N+1)]

d[1][1] = 1

for i in range(2,len(d)):
    for j in range(len(d[i])):
        if j == 0 : d[i][j] = d[i-1][0] + d[i-1][1]
        elif j == 1 : d[i][j] = d[i-1][0]
            
print(sum(d[N]))