[Baekjoon] DP - 2193 이친수

문제

2193번: 이친수

 

풀이

"""
이친수

1. 0으로 시작하지 않는다.
2. 이친수에서 1이 "두번 연속"으로 나타나지 않는다.

N자일 때, 이친수의 개수는?

d[n]: n자리일 때, 0으로 끝나는 이친수의 개수 => 0과 1로 2개씩 생김
a[n]: n자리일 때, 1로 끝나는 이친수의 개수 => 다음은 0으로 끝남
"""
n = int(input())


def solution(n):
    d = [0] * (n + 1)
    a = [0] * (n + 1)
    a[1] = 1

    for i in range(2, n + 1):
        d[i] = a[i - 1] + d[i - 1]
        a[i] = d[i - 1]

    return d[n] + a[n]


print(solution(n))

 

채점 결과