[프로그래머스] 2 x n 타일링 (Python)

문제 링크

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

프로그래머스

 

문제 설명 

가로 길이가 2이고 세로 길이가 1인 직사각형 타일로 세로의 길이가 2이고 길이가 n인 바닥을 채우는 문제이다.

제한 사항

• 가로의 길이 n은 60,000 이하의 자연수입니다.
• 경우의 수가 많아질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.

 

풀이

dp문제이므로 점화식을 찾아서 값을 return하면 되는 문제이다.

n = 1일 때, result = 1

n = 2일 때, result = 2

n = 3일 때, result = 3

n = 4일 때, result = 5 이므로

 

점화식은

 

 

✅ Code - 성공

def solution(n):
    answer = 0
    
    if n == 1:
        return 1
    elif n == 2:
        return 2
    
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = (dp[i - 2] + dp[i - 1]) % 1000000007

    return dp[n]

 

※ 참고

dp 리스트가 아닌 마지막 값에 1,000,000,007으로 나눈 나머지를 return하면 값이 너무 커지므로 효율성 테스트에서 시간초과가 난다. 따라서, n 값을 구할 때 미리 1,000,000,007로 나눈 나머지를 구하여 n 값을 작게 하여 시간을 줄여야 한다.