1. 문제

출처: 백준 1904번 01타일

2. 풀이

$n$번 째에 가능한 숫자들은 $(n-1)$번 째 숫자들의 뒤에 1을 붙이는 것과 $(n-2)$번 째 숫자들의 뒤에 00을 붙이는 것으로 찾을 수 있다.

이때, 가능한 숫자가 꽤 커서 쭉 계산한 이후에 나머지를 계산하면 시간 초과가 발생한다.

개수가 $15746$을 넘는다면, 미리미리 나머지를 구해서 넣어주도록 하자.

$a = bQ + r_1$, $c = dQ+r_2$ 라고 하면
$a+c = (b+d)Q + (r_1+r_2)$ 이므로, 첫 항은 자연스레 나머지와 관련이 없다.
결국 나머지들의 합의 나머지를 구하는 것과 같은 결과가 나오게 된다.

3. 소스코드

n= int(input())
memo = [1,2]
result = 0
if n == 1 or n == 2:
    result = memo[n-1]
else:
    for i in range(3,n+1):
        temp = memo[0] + memo[1]
        if temp >= 15746:
            memo.append(temp%15746)
        else:
            memo.append(temp)
        memo = memo[1:3]
    result = memo[1]
print(result)

4. 그 외