[BOJ][Python]1904 풀이

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

1904번: 01타일

n = int(input())
if n == 1 or n == 2 or n == 3:
    print(n)
else:
    dp = [0 for _ in range(n+1)]
    dp[1], dp[2] = 1, 2
    for i in range(3, n+1):
        dp[i] = (dp[i-1] + dp[i-2])%15746
    print(dp[n])

뻔한 dp 문제입니다. n 범위 때문에 index 에러가 나니까 예외처리를 하거나 n이 1,000,000일 때 까지 미리 구해도 됩니다. 다만 메모리 에러 때문에 미리 15746의 나머지를 구해서 저장을 해야 하는데 그러면 중간에 15746이 넘는 값들은 제대로 된 값이 저장이 되는게 아닌데 이래도 되나 싶겠지만 상관없습니다.

 

나머지 연산은 피보나치 수열에 수학적인 영향을 미치지 않습니다. 

(a + b) % p = ((a % p) + (b % p)) % p (덧셈의 나머지 연산 규칙)

대충 3, 5, 4를 사용해봅시다. (3 + 5) % 4 = 0, ((3 % 4) + (5 % 4)) % 4 = 0 으로 같은 걸 확인할 수 있습니다.