이친수 [백준 2193] - python

import sys
input = sys.stdin.readline

def BOJ2193() :
  n = int(input())
  dp = [[0 ,0] for _ in range(91)]
  dp[1] = [0, 1]
  dp[2] = [1, 0]
  for i in range(3, 91) :
    dp[i] = [sum(dp[i-1]), dp[i-1][0]]

  print(sum(dp[n]))

BOJ2193()

 

접근 방법

 

1. 1은 연속될 수가 없다.  숫자를 이어 붙일수 있는 건 이전의 숫자에 영향을 받게되므로 dp를 이용하게 되었다.

2. dp 배열은 끝자리가 0, 1로 끝나는 수의 개수를 의미한다.

3. n 자리수에서 끝자리가 0이 되는 경우는 n-1 자리수의 합, 끝자리가 0이 되는 경우의 수는 n-1자리수에서 끝이 0으로 끝나는 숫자의 개수이다.

4. 3번의 내용을 점화식으로 작성하면 된다.

 

 

 

 

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

2193번: 이친수