BOJ-2193 이친수

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

문제 소개

0으로 시작하지 않으며, 1이 두 번 연속으로 나타나지 않는 수를 이친수라고 했을 때, n자리 이친수의 개수를 구하는 문제이다.

문제 풀이

dp로 풀이하였다. 리스트 dp의 n번째 원소는 n자리 이친수의 개수를 의미하며, dp[n][0]과 dp[n][1]은 각각 n자리 이친수 중 0과 1로 끝나는 수의 개수를 의미한다.

주어지는 n의 범위는 $1 \le n \le 90$ 이지만, dp[n]을 n자리 이친수로 접근하도록 0번째 인덱스에 (0, 0)을 추가해 두었다.

n + 1자리 이친수 중 0으로 끝나는 수의 개수는 n자리 이친수의 개수와 같고, 1로 끝나는 수의 개수는 n자리 이친수 중 0으로 끝나는 개수와 같다.

이것을 점화식으로 나타내면 아래와 같다.

\[\begin{cases} dp[n + 1][0] = dp[n][0] + dp[n][1] \\ dp[n + 1][1] = dp[n][0] \end{cases}\]

이제 반복문으로 dp[n]을 구할 수 있다.

코드

# dp[n] 은 n자리 이친수의 개수
dp = [(0, 0), (0, 1)]
n = int(input())

for _ in range(n - 1):
    dp.append((dp[-1][0] + dp[-1][1], dp[-1][0]))

print(dp[-1][0] + dp[-1][1])