백준 알고리즘 2193번 이친수(python)

기본적인 다이나믹 프로그래밍 문제이다.

평범하게 다이나믹 프로그래밍으로 풀면 아래 코드와 같다. 마지막 자리가 0인 숫자 뒤에는 0과 1 2개를, 마지막 자리가 1인 숫자는 0 1개를 추가할 수 있다는 점을 이용하면 된다.

 

N = int(input())
dp = [0]*91
dp[1] = dp[2] = 1
for i in range(3, N+1):
    dp[i] = dp[i-2]*2 + dp[i-3]
print(dp[N])

결과를 보면 1, 1, 2, 3, 5, 8... 과 같은 규칙이 있어서 아래 코드 같이 쉽게 풀 수도 있다.

N = int(input())
a = b = 1
for i in range(3, N+1):
    a, b = a+b, a
print(a)