알고리즘: 백준 2193번 이친수 (feat.Python)

---

 

예시를 들어서 문제를 좀 더 자세히 뜯어 봅시다.

 

 

 

f(N) = N 자리 이친수의 개수 라고 할때,

 

N = 5 인 상태 즉, f(5)는 어떻게 구성되어 있을까요?

 

우선 N = 5 일때 이친수는 다음과 같습니다. 

 

10101

10100

10010

10001

10000

 

 

 

 

이것들을 가장 처음 1을 제외한 그 다음 1을 기준으로 쪼개보면 다음과 하나의 규칙을 발견할 수 있습니다. 

 

10101    

10100

 

f(3)과 모양이 같고

 

 

 

100010

 

f(2)와 모양이 같고

 

 

 

100001

 

f(1)과 모양이 같습니다. 

 

 

 

100000

 

N = 0 는 정의되어 있지는 않지만 

 

f(0) = 1이라고 합시다. 

 

 

 

 

 

이렇게 봤을 때 

 

f(5) = f(3) + f(2)  + f(1) + f(0) 이라고 할 수 있겠군요!

 

 

그런데 여기서 또 살펴보면 

 

f(2) + f(1) + f(0) = f(4) 네요?

 

 

한번 더 정리 해보면

 

f(5) = f(4) + f(3) 

 

이런 모양이 나오고 이는 피보나치 수열 형태와 같네요

 

 

 

그렇다면 점화식은 

 

f(1) = 1

f(2) = 1

 

f(n) = f(n - 1) + f(n - 2) (단, n >= 3)

 

 

라고 할 수 있겠습니다. 

 

 

 

import sys


input = sys.stdin.readline  # 더 빠르고 가벼운 입력을 위해

n = int(input())

table = [1, 1]  # f(1)과 f(2)를 넣어줍니다.

for i in range(2, n):

    table.append(table[i - 1] + table[i - 2])


print(table[n - 1])

 

3
2

Process finished with exit code 0