[python] 프로그래머스 - 2 x n 타일링

출처 : 프로그래머스 코딩테스트 연습, https://programmers.co.kr/learn/courses/30/lessons/12900

코딩테스트 연습 - 2 x n 타일링

 

 

첫 번째 풀이 : 시간초과

 

def solution(n):
    dp = [1 for _ in range(n+1)]
    
    dp[2] = 2
    
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2]

    return dp[n] % 1000000007

 

풀어본 문제라고 생각하고 아무 생각없이 풀었는데 바로 시간초과 나왔다. 세상에

 

두 번째 풀이

 

def solution(n):
    prepre = 1
    pre = 2
    
    for _ in range(3, n+1):
        pre, prepre = prepre + pre, pre

    return pre % 1000000007

 

시간복잡도 상으로는 O(N)이라서 더 이상 줄이는건 불가능하다고 보고

dp 배열을 선언하는 과정에서 O(N)이 O(2N)이 되는 데서 시간이 오래걸리는게 아닐까 생각해

배열 선언을 없애버렸더니 풀렸다.

---

 

시간 복잡도

 

O(N)

 

알게 된 점

 

자료의 개수가 엄청날 경우 O(2N)조차도 오래 걸릴 수 있다.

배열 선언에도 시간이 걸리니 주의할 것!

 

고찰

 

-