[1904] 01타일

1904번: 01타일

00과 1로만 가능한 조합을 찾는 문제이다. N이 1~6인 수까지 조합을 모두 적다보면, 패턴이 보이는 문제이다.

바로 피보나치!!

N=1, [1]
N=2, [11, 00]
N=3, [111, 001, 100]

1,2,3 까지 보면, 이전 것에 숫자를 붙이는 형식으로 표현이 가능해진다. N=3을 기준으로 본다면, N-2인 1일 때 뒤에 00을 붙이는 경우와 N-1인 2일 때 뒤에 1을 붙이면 N=3인 경우와 경우의 수가 맞는다.

혹시 모르니 5까지 이어서 보면…

N=4, [1111, 0011, 1001, 1100, 0000]
N=5, [11111, 00111, 10011, 11001, 00001, 11100, 00100, 10000]

으로 각각 N-2에 00을 붙이는 경우 + N-1에 1을 붙이는 경우가 현재 N의 경우의 수임을 알 수 있다.

여기서 N을 15746로 나누는 것도 잊지 말고 해야한다.(이것 때문에 많이 틀렸다.)

풀이

if __name__ == "__main__":
    N = int(input())
    a1 = 1
    a2 = 2
    if N < 3:
        print(N)
    else:
        before = ()
        for i in range(3, N + 1):
            if i == 3:
                before = (a1, a2)
            else:
                before = (before[1], (before[0] + before[1]) % 15746)
        print((before[0] + before[1]) % 15746)