2 x n 타일링

🔗 문제 링크

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

❔ 문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

1. 타일을 가로로 배치 하는 경우

2. 타일을 세로로 배치 하는 경우

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

⚠️ 제한사항

• 가로의 길이 n은 60,000이하의 자연수 입니다.

• 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

---

💡 풀이 (언어 : Python)

규칙성을 이용해서 푸는 문제였는데, 처음엔 단순한 수열 규칙을 발견 못하고 수학적 공식을 유도해서 풀었다.

import math

def solution(n):
    # 직사각형 세워서 다 채우는 경우를 카운트 
    answer = 1
    # n을 2로 나눈 몫, 나머지
    quo, rem = divmod(n, 2)
    
    # 2로 나눈 몫 1부터 quo까지 경우의 수 계산해서 더해줌
    for i in range(1, quo+1):
        res = n - (2*i)
        answer += math.factorial(i+res) // ( math.factorial(i) * math.factorial(res) )
    
    return answer % 1000000007

이렇게 풀었더니 답은 모두 정확했지만 효율성 검사에서 시간초과가 떴다.
모듈을 사용해도 팩토리얼 계산이 오래 걸리는 듯하다.
풀이를 보니 이 문제는 단순한 피보나치 수열이었다?! 왜 발견 못했을까...
시간 복잡도를 줄이기 위해 DP를 이용해 풀어야만 정답이다.

def solution(n):
    
    # 피보나치 수열 계산 시간 줄이기 DP
    d = [0 for i in range(n+1)]
    # 피보나치 수 1, 2일 때
    d[1], d[2] = 1, 2 

    # 피보나치 수 n에 도달할 때까지 모두 다 계산
    for i in range(3, n+1):
        # 전의 결과들을 더해서 답을 도출하므로 나누기를 매 과정마다 해줘야 함
        d[i] = (d[i-1] + d[i-2]) % 1000000007
    
    return d[n]