(Python/파이썬) 백준 2193번 - 이친수

문제출처: https://www.acmicpc.net/problem/2193

2193번: 이친수

1. 코드

#n이 0일때 0개
#n이 1일때 1개
#n이 2일때 1개
pinary =[0,1,1] 
 
for i in range(3,91):
    pinary.append(pinary[i-2]+pinary[i-1])
 
 
 
n = int(input())
print(pinary[n])

2. 해결과정

0으로 시작을 해서는 안되기 때문에 처음은 1이여야 하고, 1은 두번 연속으로 나타나지 않아야한다.

규칙을 찾아보면 예를 들어 n=5일때 이친수는 10/101, 10/100, 뒷자리 3자리는 n=3일때 숫자와 동일하고, 10/010,10/001,10/000은 뒷자리 3자리가 n=4일때 1뒤의 숫자와 동일하다는 것을 알 수 있다. 따라서 pinary[i-2]+pinary[i-1]이라는 점화식을 도출해낼 수 있다.

 

n=0일때 이친수는 0개

n=1일때 이친수는 1개

n=2일때 이친수는 10으로 1개이므로

pinary리스트에 미리 저장을 해두고 3부터 반복문을 돌려준다.

 

3. 느낀점

규칙만 찾으면 쉽게 풀 수 있었던 문제였다. dp가 어렵긴하다...