[백준 2193번] 파이썬 - 이친수

백준 2193 - 이친수

시간 제한 2초, 메모리 제한 128MB

# 조건

• 0과 1로만 이루어진 수를 이진수라 한다. 이러한 이진수 중 특별한 성질을 갖는 것들이 있는데, 이들을 이친수(pinary number)라 한다.
• 이친수는 다음의 성질을 만족한다.
  1. 이친수는 0으로 시작하지 않는다.
  2. 이친수에서는 1이 두 번 연속으로 나타나지 않는다. 즉, 11을 부분 문자열로 갖지 않는다.
• 예를 들면 1, 10, 100, 101, 1000, 1001 등이 이친수가 된다. 하지만 0010101이나 101101은 각각 1, 2번 규칙에 위배되므로 이친수가 아니다.
• N(1 ≤ N ≤ 90)이 주어졌을 때, N자리 이친수의 개수를 구하는 프로그램을 작성하시오.

# 접근 방법

• DP를 이용하여 풀어주었다.
• 이친수의 경우 이전 자리수가 0으로 끝난 이친수에서는 0과 1을 붙여 2개가 나올 수 있고, 1로 끝난 이친수에서는 0만 붙일 수 있다.
• 따라서, DP를 [N+1][2] 크기로 생성해주고 채워나간다.
• DP[1]을 [0, 1]로 세팅하여 0으로 끝난 개수 0개, 1로 끝난 개수 1개로 설정해준다.
• DP[2] (2자리 이친수)의 경우 DP[2][0] = DP[I-1][0] + DP[I-1][1]로 변경, DP[2][1] = DP[I-1][1]로 변경해주면서 n+1까지 채워나가면 된다.

import sys
sys.stdin = open('input.txt')
input = sys.stdin.readline

N = int(input())
dp = [[0, 0] for _ in range(N+1)]
dp[1] = [0, 1]

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

print(sum(dp[N]))