백준 1904번: 01타일 (Python)

접근

N이 증가함에 따라 변화하는 타일 배열 수

N	타일 배열	배열 수
1	'1'	1
2	'11' '00'	2
3	'111' '100' '001'	3
4	'1111' '1100' '1001' '0011' '0000'	5
5	'11111' '11100' 11001' '10011' '00111' '10000' '00100' '00001'	8
6	'111111' '111100' '111001' '110011' '100111' '001111' '110000' '100100' '001100' '100001' '001001' '000011' '000000'	13

정말 신기하게도 피보나치 수열의 배열과 동일하게 증가하게 된다.

코드

n = int(input())
num = [0, 1, 2]
if n > 2:
    num = num + [0] * (n - 2)
    for i in range(3, n + 1):
        num[i] = (num[i - 1] + num[i - 2]) % 15746
print(num[n])

N의 수가 매우 크기 때문에 피보나치 수를 N까지 모두 계산한 후에 결과를 15746으로 나누려고 하면 메모리가 초과되게 된다.

더 생각해 볼 것?

우연히 피보나치 수의 배열을 갖는 것을 알아채 쉽게 풀었지만 왜 그런 결과가 나오는지 생각해보았다.

그리고 또 우연히도 N - 1 배열의 각 타일 맨 앞에 1을 추가하고, N - 2 배열의 각 타일 맨 뒤에 00을 추가하여 합칠 경우 중복됨 없이 N 배열의 타일이 나온다는 것을 찾았다. 하지만 이 또한 피보나치 수열이라는 것을 알고나서야 찾을 수 있었기 때문에... 왜 이 수열이 나와야 하는지는 아직 이해를 못했다.