[백준 2193번] 이친수

https://www.acmicpc.net/problem/2193

2193번: 이친수

2023.04.14 - [코딩 테스트/개념] - dynamic programming

# 1 ≤ N ≤ 90

import sys

readline = sys.stdin.readline

N = int(readline())

# d[n] = n자리 이친수 개수
# d[i] = d[i - 1] + d[i - 2]
# init: d[1] = 1, d[2] = 1

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

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

print(d[N])

점화식은 주석에 작성한 것과 같다. n자리 이친수의 끝자리가 0이면 n-1번째 자리에 1이나 0 모두 상관 없으므로 d[i - 1]이고, n자리 이친수의 끝자리가 1이면 n - 1번째 자리는 무조건 0이어야 한다. 따라서 d[i - 2]와 같다. n자리 이친수의 끝자리는 0 또는 1이므로 두 경우의 수를 더해서 점화식이 나왔다.

d를 초기화할 때 range(N + 1)이 아니라, range(N + 2)를 한 이유는 N의 범위가 1부터이기 때문이다. 뒤에 초기화문에 d[2]도 1로 초기화하는데, 주어진 N이 1이면 d[2]에 접근할 때 IndexError가 발생한다. 그래서 1을 더해주었다.