[BOJ] 백준 11727. 2×n 타일링 2

🥈2×n 타일링 2

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

💡아이디어

그림그려보면 규칙 찾는 것은 금방 찾을 수 있었다.

그러나 생각보다 식을 구하는 게 쉽지는 않았던 ,,

전전꺼 * 2 + 전에꺼 = 현재꺼

라는 식을 구해낼 수 있었다!

✒️ 풀이

n = int(input())
dp = [0, 1, 3]

if n <= 2:
    print(dp[n])
    
else: 
    for i in range(3, n+1):
        dp.append(dp[i-2]%10007 * 2 + dp[i-1]%10007)
    print(dp[n]%10007)
        

시간이 비정상적으로 많이 소요되는 듯 해서

애초에 append 해줄때 나누어 줬는데, 결과적으로 비슷한 시간이 소요됐다.

답을 구하고 나누던, 그렇지 않던 비슷한 것 같다.

구글링을 많이 해봤으나 대부분 다 비슷하게 풀이해서,, 시간을 줄이는 방법을 알아내진 못했다 😢