[프로그래머스] 파이썬 _ 2 x n 타일링

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

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

 

문제유형 : DP

 

문제풀이:

• n일때 가짓수는 n-1일때의 가짓수 + n-2일때의 가짓수이다.
  • n-1에다가 가로길이가 1인 세로로 길쭉한 사각형을 각각 붙이는 경우
  • n-2에다가 가로길이가 2인 가로로 길쭉한 사각형을 각각 붙이는경우
  • 위 두경우를 더한것이 n일때의 갯수이다.

 

정답코드 :

백준에서 똑같은 문제를 풀어봐서 바로 생각나서 풀수 있었다!

def solution(n):
    answer = 0
    # n이 1일때 방법 - 1가지 ( 세로)
    # n이 2일때 방법 - 2가지 (가로,세로)
    # n이 3일때 방법 - 3가지
    # n이 4일때 방법 - 5가지
    dp = [0,1,2]


    for i in range(3,n+1):
        dp.append((dp[i-1]+dp[i-2])%1000000007)


    return dp[-1]