[프로그래머스] 2 x n 타일링

문제

출처

이해

입력

• n
  • 타입: 자연수
  • 범위: [1, 6만]

출력

• 주어진 타일로 세로의 길이가 2이고 가로의 길이가 n인 바닥을 채우는 경우의 수

조건

1. 타일은 2 x 1 크기이고 회전시킬 수 있다.
2. 타일은 격자에 딱 맞게 배치해야 한다.
3. 경우의 수가 커질 수 있으므로 10억 7로 나는 나머지를 return한다.

예시

입력: 4

출력: 5

접근

채워야할 면적의 세로 길이가 2칸이므로 채울 때 사용하는 패턴은 두 가지뿐이다.

1. 
2. 

나머지 모든 패턴은 이 두 가지 패턴으로 쪼갤 수 있는 패턴이거나 아니면 면적을 완전히 채우지 못하는 패턴이다. 따라서 바닥을 채우는 모든 패턴은 이 두 가지 패턴의 순열로 표현할 수 있다는 것을 알 수 있다.

가로 길이가 n인 면적을 채우는 경우의 수를 DP(n)이라고 해보자. n인 면적을 채우는 패턴에서 뒤에 1번 또는 2번 패턴을 붙이면 n+1 또는 n+2인 면적을 채우는 경우의 수에 영향을 미친다는 것을 알 수 있다. 거꾸로 생각해보면 DP(n)으로 올 수 있는 경우는 DP(n-1)에서 1번 패턴이 더해진 경우와, DP(n-2)에서 2번 패턴이 더해진 경우 뿐이라는 것이다. 따라서 다음과 같은 점화식을 만들 수 있다.

\[\text{DP}(n) = \text{DP}(n-1) + \text{DP}(n-2)\]

n = 1일 때와 n = 2일 때의 초기값은 자명하게 1, 2이므로 n = 3부터 반복적으로 계산하면 답을 구할 수 있다.

구현

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

직전 2개만 계산에 필요한다는 점에 착안하여 변수를 재활용하는 방법도 있다.

def solution(n):
    a, b = 1, 2
    for i in range(2, n):
        a, b = b, (a + b) % 1000000007
    return b