[백준 11726 2xn 타일링] PYTHON

 

sol(1)=1

sol(2)=2

sol(3)=3

이런식으로 sol(n)=sol(n-1)+sol(n-2)다.

간단히 규칙을 찾고 코딩을 시작했다

 

from sys import stdin

def sol(n):
    if n==1:
        return 1
    elif n==2:
        return 2
    return sol(n-1)+sol(n-2)
if __name__ == "__main__":
    t=int(stdin.readline())
    print(sol(t)%10007)

여기까진 좋았는데 시간 초과가 뜬다...

아마 문제는 회귀 시 depth가 너무 깊어진 것 같다.

for 문으로 바꿔 문제를 다시 풀어봤다

 

def sol(n):
    tmp_arr=[0,1,2]
    for i in range(3,n+1):
        tmp_arr.append(tmp_arr[i-2]+tmp_arr[i-1])
    print(tmp_arr[n]%10007)
if __name__ == "__main__":
    t=int(input())
    sol(t)

 

CLEAR!!!