백준2193 - 이친수 (DP) Python

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

문제는 N자리의 이친수 (0으로 시작하지 않으며, 1이 두번으로 나타나지 않는 수)의 갯수를 구하는 문제다.

직접 써보며 점화식을 구할 수 있을 것 같아 각 N자리에 몇 개의 이친수가 존재하는지 헤아렸다.

'''
1 : 1 / 1 
2 : 10 / 1
3 : 100 101 / 2
4 : 1000 1001 1010 / 3
5 : 10000 10001 10010 10100 10101 / 5
6 : 100000 100001 100010 100100 101000 100101 101001 101010 / 8
'''

헤아리다보니 [1,1,2,3,5,8] 라는 익숙한 수의 조합이 등장한다.

 

보였다! 틈새의 점화식!

 

전체 소스 코드

import sys
data_temp = sys.stdin if sys.platform == 'linux' else open('입력.txt', 'r')
input_data = data_temp.read()

def solution (data) :
  n = int(data)
  dp = [0] * (n + 1)
  dp[0] = dp[1] = 1
  if n > 1 : dp[2] = 1 
  
  for i in range(3, n+1) :
    dp[i] = dp[i-1] + dp[i-2]
    
  print(dp[-1])
  
solution(input_data)