[프로그래머스] Level 2 - 3xn 타일링 (Python)

 

 

 

 

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

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

 

 

 

 

✅ Solution

• n이 홀수일 땐 항상 답은 0이다.
• f(2) = 3, f(4) = 11, f(6) = 41, f(8) = 153 
  • f(n) = f(n-2) * 4 - f(n-4)
  • f(n-2) * 4 보다 f(n-4)가 더 크면 음수가 나오기 때문에 모듈러 분배 법칙을 이용하여 처리한다.

 

 

 

 

 

✅ Code

def solution(n):
    if n % 2 == 1:
        return 0
    
    dp = [3, 11]
    
    for i in range(2, n//2 + 1, 1):
        dp.append(((dp[i-1] * 4 % 1000000007) - dp[i-2] % 1000000007 + 1000000007) % 1000000007)  
    
    return dp[n//2-1]

 

 

 

 

 

📝 Today I Learned

모듈러 연산의 분배 법칙

• (a + b) % m = ((a % m) + (b % m)) % m
• (a * b) % m = ((a % m) * (b % m)) % m
• (a - b) % m = ((a % m) - (b % m) + m) % m