Lv2. 2 x n 타일링

문제 보기 :  2 x n 타일링

프로그래머스

---

문제

• 정답률 : 56%

 

---

작성 코드 & 풀이

# 1차 작성 코드

import math

def solution(n):
    answer = 0
    num1 = n//2
    num2 = n%2

    while num1 > -1:
        method = math.factorial(num1+num2) // (math.factorial(num1)*math.factorial(num2))
        answer += method%1000000007
        num1 -= 1
        num2 += 2
    
    return answer%1000000007

처음엔 1 타일의 수와 2 타일의 수를 가지고 팩토리얼을 적용해서 개수를 구해 더하는 방법으로 작성했다. 

정답은 맞지만 시간이 오래걸린다는 문제가 있어서, 다른 방법을 생각해봤고 그러려면 예제가 더 필요할 거 같아서 
print(solution(숫자))로 예제를 더 구했다. 

이렇게 나오는 걸 볼 수 있는데 잘 보면 이거.... 피보나치 수열이잖아?

그래서 바로 노선 변경해서 피보나치 수열로 구하는 것으로 고쳤다.

def solution(n):
    answer = 0
    num = [1,1]
    an = 1
    
    while an != n:
        num.append(sum(num))
        num = num[1:]
        an += 1
    answer = num[-1]
    return answer%1000000007

num에 계속 append하고 싶었지만 그렇게 하면 시간초과가 나는 바람에,,
리스트가 좋은 자료형이지만 무겁다는 단점을 잊었다.

그래서 num[1:]를 적용해 무조건 2개로 원소 갯수를 유지하도록 했다.

이렇게 하면 정확성 테스트 & 효율성 테스트 모두 통과할 수 있었다.