[Python] Baekjoon - 2193. 이친수

백준 2193번 이친수 문제는 N 자리 이진수 중 맨 앞자리 수가 0이 아니면서 1이 연속해서 등장하지 않는 이친수의 개수를 구하는 문제다. 다이나믹 프로그래밍을 이용해서 해결할 수 있는 문제인데, 점화식을 세워서 정리하면 결국 피보나치수열의 N 번째 수를 구하는 문제다.

 

백준 2193번 이친수 문제 정보

알고리즘 분류

- 다이나믹 프로그래밍

난이도

- 실버 3

 

이친수 문제 요약

N자리 이진수 중 맨 앞이 0이 아니고 1이 연속해서 등장하지 않는 이친수의 개수를 구하는 문제다.

 

문제 풀이 과정

N-1자리 이친수 중 마지막이 0인 수의 뒤에는 0과 1이 붙을 수 있고, 마지막이 1인 수의 뒤에는 0만 붙을 수 있다.

P[n] = zero[n] + one[n]
zero[n] = zero[n-1] + one[n-1] = P[n-1]
one[n] = zero[n-1] = zero[n-2] + one[n-2] = P[n-2]
=> P[n] = P[n-1] + P[n-2] (피보나치수열)

 

코드

코드 설명

피보나치수열의 N번째 수를 구한다.

N = int(input())

pre, current = 0, 1
for _ in range(N-1):
    pre, current = current, pre + current

print(current)