백준 알고리즘 - 이친수 (2193) [Python]

 문제

 

www.acmicpc.net/problem/2193

2193번: 이친수

 

 

 

 

 

 문제 상황

 

- 11은 올 수 없다, 0으로 시작할 수 없다는 두가지 규칙으로 수를 만들 때, 입력받은 N자리 수로 가능한 이친수를 계산한다.

 

 

 

 

 

 해결 전략

 

- 가능한 수의 개수를 결정하는 것은 결국 1의 자리이다. 1의 자리를 관찰하고 그 수를 기록한다.

 

 

 

 

 

 코드

 

from sys import stdin
input = stdin.readline
N = int(input())
counts = 1
base = [0, 1] # 0번 인덱스 = 0의 개수, 1번 인덱스 = 1의 개수
while True:
    if counts == N: break
    counts += 1
    temp = [0,0]
    temp[0] = base[0] + base[1]
    temp[1] = base[0]
    base = temp
print(sum(base))

 

 

 

 해설

 

- dp로 안내받았지만 생각해보면 dp는 괜한 메모리 낭비가 된다. cache를 저장할 필요없이 N까지 계속 연산을 반복해주어 결과만 도출하면 된다.

 

 

 

 

 

 새로 학습한 것 & 실수 

 

- .