#98 백준 파이썬 [1904] 01타일 - 점화식

https://www.acmicpc.net/problem/1904

 

#Solution

이 문제의 경우 이진수의 길이에 상관 없이 1 혹은 00으로 끝나면 되면 된다. 즉 피보나치 수열과 같이 점화식으로 표현하면 되는 것이다. 1 2 3 5 8 ... 그러나 일반적인 피보나치 수열로 표현할 시에 수가 너무 커져서 시간 초과를 출력한다. 정답은 어차피 나머지이므로 for문에서 n-1, n-2를 더할 때 15746으로 나눈 나머지로 치환해서 더해주어도 무관하다. 나눗셈과 나머지의 특징을 잘 생각해보면 될 것.

def tile001(n):
    answer = 0
    temp_1 = 1
    temp_2 = 2
    for i in range(1, n+1):
        if i == 1:
            answer = temp_1
        elif i == 2:
            answer = temp_2
        else:
            answer = temp_1 + temp_2
            temp_1 = temp_2 % 15746
            temp_2 = answer % 15746
    
    print(answer % 15746)
        
tile001(int(input()))