백준 1904 01타일

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

규칙은 찾았다. N=1 -> 1, N=2 -> 2 이고,
N=3일때는 끝자리가 1일때와 00일때를 구해서 더하면 된다. 그럼 결국 N=2일때와 N=1일때 경우의수를 더하면 된다. 결국 피보나치이다.

그런데 재귀함수 형태로 푸니까 테스트케이스는 맞는데 깊이를 자꾸 초과한다고 나온다.

import sys

def tile(N):
    if N == 1:
        return dp[1]
    elif N == 2:
        return dp[2]

    dp[N] = tile(N-1) + tile(N-2)
    return dp[N]

N = int(sys.stdin.readline().strip())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
print(tile(N) % 15746)

찾아보니 재귀함수는 성능이 안좋다고 한다.
그래서 그냥 일일히 계산해보니까 된다.

import sys
N = int(sys.stdin.readline().strip())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2

for i in range(3, N+1):
    dp[i] = (dp[i-1] + dp[i-2])%15746
print(dp[N])