BOJ 1904 01타일

https://www.acmicpc.net/problem/1904
시간 0.75초, 메모리 256MB
input :

• N(1 ≤ N ≤ 1,000,000)

output :

• N인 모든 2진 수열의 개수를 15746으로 나눈 나머지를 출력

조건 :

• N=1일 때 1만 만들 수 있고, N=2일 때는 00, 11을 만들 수 있다. (01, 10은 만들 수 없게 되었다.) 또한 N=4일 때는 0011, 0000, 1001, 1100, 1111 등 총 5개의 2진 수열

---

DP[i] = DP[i - 1] + DP[i - 2] 의 규칙을 가진다.

2n타일링 할 떄 와 같이.
이진수 1을 1개 추가하는 경우,
이진수 00을 추가하는 경우로 나뉜다.

이 문제에서 그냥 백만개 만들고, 나머지 계산을 나중에 하니.
메모리 초과, 시간 초과가 그냥 발생한다.

일단 메모리 줄이기 위해서 변수 2개만 저장해서 스왑 하듯 계산을 하자.

previous = 1
current = 2

temp = previous
previous = current
current = previous + temp

그런데. 나머지 계산에도 시간이 매우 소모되는 것 같다.

current = (previous + temp) % 15746을 하는 경우에는


1.86 2.11 초 사이가 나옴.

current = previous + temp 로 계산을 하고 마지막에 출력을 할 때 나머지를 구하면?

이런 차이가 생기니까 나머지 계산은 숫자를 계산 할 때 같이 하도록 하자.

정답 코드 :

import sys

n = int(sys.stdin.readline())
previous = 1
current = 2

for i in range(1, n):
    temp = previous
    previous = current
    current = (current + temp) % 15746

print(previous)