Programmers, 연습문제, DP, ‘2 x n 타일링’

프로그래머스 연습문제 중 12900번 ‘2 x n 타일링’

https://school.programmers.co.kr/learn/courses/30/lessons/12900?language=python3

문제설명

가로 길이가 2이고 세로의 길이가 1인 직사각형모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 2이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다.

• 타일을 가로로 배치 하는 경우
• 타일을 세로로 배치 하는 경우

예를들어서 n이 7인 직사각형은 다음과 같이 채울 수 있습니다.

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

제한사항

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

입출력 예

n	result
4	5

입출력 설명 예

입출력 예 #1 다음과 같이 5가지 방법이 있다.

---

풀이

다이나믹 프로그래밍을 하면 떠오르는 대표적인 문제 중 하나이다.

• 타일이 1개인 경우는 dp[1] = 1 이다.
• 타일이 2개인 경우는 dp[2] = 2 이다.
• 타일이 3개인 경우는 (타일 1개인 경우) + (가로 타일 2개)를 고려하면 된다. dp[3] = 3 이다.
• 타일이 4개인 경우는 (타일 2개인 경우) + (가로 타일 2개), (타일 3개인 경우) + (세로 타일 1개)를 고려하면 되고, 이를 식으로 표현하면 dp[4] = d[2] + d[1]이다.

• 타일이 5개인 경우는 (타일 3개인 경우) + (가로 타일 2개), (타일 4개인 경우) + (세로 타일 1개)를 고려하면 되고, 이를 식으로 표현하면 dp[5] = d[4] + d[3]이다.

  ……

• 타일이 n개인 경우는 (타일 n -2개인 경우) + (가로 타일 2개), (타일 n - 1개인 경우) + (세로 타일 1개)를 고려하면 되고, 이를 식으로 표현하면 dp[n] = d[n - 2] + d[n - 1]이다.

이를 코드로 나타내면 다음과 같다. 주의할 점은 계속된 덧셈으로 파이썬의 최대 정수 범위인 2³¹-1을 넘어 오버플로우가 되지 않도록 1000000007로 나눈 나머지로 계산 하는 것이다.

def solution(n):
    dp = [-1] + [0] * n
    dp[1], dp[2] = 1, 2 
    for i in range(3, n + 1):
        # 오버플로우 방지
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007
    return dp[n]