[백준/Python3] 2193 이친수

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

---

풀이

이진수 중 0으로 시작하지 않으며, 1이 두 번 연속으로 나오지 않는 수인 이친수의 조건을 만족하면서 길이가 N인 모든 수의 개수를 구하는 문제다.

2차원 dynamic table을 이용해 해결했다. 정의는 아래와 같다.

dp[i][j] # 길이가 i이며 j로 끝나는 이친수의 개수

이때 N의 길이를 가지는 이친수의 개수는 N의 길이를 가지며 0으로 끝날 때와 1로 끝날 때를 더한 값과 같은데 각각은 다음과 같이 구할 수 있다.

dp[N][0] = dp[N-1][0] + dp[N-1][1]
dp[N][1] = dp[N-1][0] # 1이 중복해서 나올 수 없으므로 dp[N-1][1]의 개수를 더할 수 없다.

# 정답
dp[N] = dp[N][0] + dp[N][1]

코드

# Initial
N = int(input()) # 1 <= N <= 90
dp = [[0 for _ in range(2)] for _ in range(91)]
answer = 0

# Make DP table
dp[1][0] = 0
dp[1][1] = 1

for i in range(2, 91):
    dp[i][0] = dp[i-1][0] + dp[i-1][1]
    dp[i][1] = dp[i-1][0]

# Answer
answer = sum(dp[N])
print(answer)