[프로그래머스|파이썬] 2 x n 타일링 (연습문제/lv.2)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/12900

프로그래머스

 

 

🐍파이썬

❌ 시간초과 실패 코드

from itertools import product
def solution(n):
    total = n + n % 2
    answer = 0
    for i in range(2, total+1):
        for j in product([1, 2], repeat=i):
            if sum(j) == n:
                answer += 1
    return answer

1과 2로 n을 만들 수 있는 경우의 수를 구하는 문제라고 생각하고 product로 다짜고짜 가능한 모든 중복순열을 만드는 식으로 접근했다가 시간초과로 실패했다. 

def solution(n):
    arr = [0 for _ in range(n)]
    arr[0], arr[1] = 1, 2
    for i in range(2, n):
        arr[i] = (arr[i-1]+arr[i-2])%1000000007
    return arr[n-1]

n과 타일 수를 살펴보면 규칙을 발견할 수 있다.

n = 1: 1 👉 1
n = 2: 2, 11 👉 2
n = 3: 21, 12, 111 👉 3
n = 4: 22, 112, 121, 211, 1111 👉 5

n = 5: 221, 212, 122, 1121, 2111, 1211, 1112, 11111 👉 8...

각 n의 타일 수는 n-1의 타일수 + n-2의 타일수이다.

이를 식으로 정리해 보면 다음과 같다.

arr[n] = arr[n-1] + arr[n-2]

 

n의 값이 최대 60000이기 때문에, 매번 경우의 수를 1,000,000,007으로 나눈 나머지를 넣어줘야 시간초과가 발생하지 않는다.

arr[n] = (arr[n-1] + arr[n-2]) % 1000000007

 

 

다른 풀이 방법

def solution(n):
    a, b = 1, 1
    for i in range(1, n):
        a, b = b, (a + b) % 1000000007
    return b