[Programmers] 2 x n 타일링 - 12900

내 첫 DP 문제.. 문제를 읽고 dp 로 풀 수 있다는 패턴을 알아내야 한다!

홀/짝일 경우로 나눠서 연산하는 과정으로 풀었는데 테케가 틀리게 된다. 따라서 dp로 풀기.

 

Question

 

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

제한사항

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

 

Point

 

• 부분 문제로 나눌 수 있는가 ?  
• 중복 계산이 발생하는가? 
• => 위 두 조건이 True이기 때문에 이 문제는 dp로 해결한다.

 

Code (After)

 

def solution(n):
    n1, n2 = 0,1
    for i in range(n):
        n2, n1 = n1+n2, n2
    
    return n2 % 1000000007

 

Code (Before)

 

from collections import deque
def solution(n):
    if n==1 : return 1
    elif n==2 : return 2  
    dp = deque([1,2])
    
    for _ in range(3, n+1):
        dp.append(dp.popleft() + dp[0])
    
    return dp[-1] % 1000000007

 

now me

On my github