2 x n 타일링

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

 

1. 분류 : 다이나믹 프로그래밍 

 

2. 풀이 : 

가장 기초적인 다이나믹 프로그래밍 문제이므로 잘 이해하고 넘어간다. 

왼쪽 부터 i-1 까지의 길이가 덮여 있으면, 2x1 을 채우는 경우의 수는 1가지 밖에 없다. 

왼쪽 부터 i-2 까지의 길이가 덮여 있으면 2x2 를 채우는 경우의 수는 2가지이지만, 모두 세로인 경우는 위의 방식에서도 count 되므로 가로로 채우는 경우의 수 1가지 라고 할 수 있다. 

따라서 점화식은 An = An-2 + An-1 이 된다. 

 

3. 유의사항 :

수가 아주 커질 수 있으므로  % 1000000007  처리를 어디서 하느냐에 따라서 효율성 문제가 걸릴 수 있다. 

나누기 연산한 값은 항상 동일하므로 dp 리스트 안에 넣는 과정에서 나눠 주자 

( answer 에 넣을 때 나누거나 return 할 때 나누면 효율성부분 점수 받기가 어렵다 )