[백준/Python] 2193번 - 이친수

문제

백준 2193번 - 이친수

해결 과정

• DP를 이용하여 풀어야함
• 규칙 찾기
  • 0일 경우에는 0개
  • 1일 경우에는 1 -> 1개
  • 2일 경우에는 10 -> 1개
  • 3일 경우에는 101, 100 -> 2개
  • 4일 경우에는 1010, 1001, 1000 -> 3개
  • 5일 경우에는 10101, 10100, 10010, 10001, 10000 -> 5개
  • 6일 경우에는 101010, 101001,101000, 100100, 100010, 100101, 100001, 100000 -> 8개
  • N일 경우 = (N-2)일 경우의 개수 + (N-1)일 경우의 개수
• DP[i] = DP[i-2] + DP[i-1]
• DP[i] 는 i자리 수의 개수를 의미

시행착오

• 시간초과 -> DP로 풀어야 함...🙄

import sys

n = int(sys.stdin.readline())

num = 0
answer = 0

while True:
  num += 1
  if len(format(num,'b')) == n:
    if format(num,'b')[0] != '0':
      if '11' not in format(num,'b'):
        answer += 1
  if len(format(num,'b')) == n+1:
    break

print(answer)

풀이

import sys

n = int(sys.stdin.readline())

dp = [0,1,1]

for i in range(3,91):
  dp.append(dp[i-2]+dp[i-1])

print(dp[n])