링크Permalink

https://school.programmers.co.kr/learn/courses/30/lessons/12902

문제Permalink

문제 설명 및 요점Permalink

• 단위 타일의 크기는 2x1 이다.
• 가로의 길이 $n$은 5000 이하의 자연수이다. 또한 세로 길이가 3 이므로, $n$은 2의 배수여야만 한다.
  • $n$이 2의 배수가 아니라면, 길이가 짝수인 단위 타일로는 넓이가 홀수인 타일을 채울 수 없다.
• 경우의 수를 1000000007로 나누어 리턴해야 한다.

풀이Permalink

#DP

• 타일링 문제는 DP로 분류된다.
  • 이전 타일 배치 경우의 수가 지속적으로 활용되기 때문이다.
• 점화식을 찾아보자. $n=2$ 인 경우는 간단하게 구할 수 있으며, $n=4$ 인 경우의 수는 문제에 주어져 있다.

$n=2$ 로 부터, $n=4$ 를 어떻게 도출할 수 있을까? dp[n] = 가로가 n일때, 3xn 타일링의 경우의 수 라고 정의해보자. dp[4] = dp[2] * dp[2] + ?로 볼 수 있다. 가로 길이 4를 2와 2로 쪼갤 수 있고, 가로 길이 2는 dp[2] 를 통해 이미 구했기 때문이다. 하지만 + ? 로 적어놨듯, 아직 구해지지 않은 무언가가 있다.

입출력 예시에도 나와있는데, 아래와 같이 $n=4$ 에서만 볼 수 있는 특이한 경우가 있기 때문이다.

따라서 + ?자리에는 2 가 들어간다.

$n=6$인 경우도 이전 케이스들을 이용하여 도출해보자. dp[4]를 통해 가로 길이가 4일 때를 계산하였고, 거기에 가로 길이 2가 늘어난 경우로 볼 수 있다. 이 경우는 dp[4] * dp[2]로 계산할 수 있다. 또한, dp[4]를 계산할 때 $n=4$ 에서만 볼 수 있는 유니크한 단위 타일도 찾았기 때문에 이 경우를 더해줘야 한다. 이는 dp[2] * 2(유니크한 단위 타일) 로 계산할 수 있다. 유니크한 단위 타일의 가로 길이가 4였기 때문에 dp[2]를 곱해주었다.

이전 경우와 마찬가지로, $n=6$ 에서만 볼 수 있는 특이한 경우가 존재한다.

유니크한 단위 타일을 잘 보면, 이것이 만들어지는 규칙을 도출해낼 수 있다. 윗변 또는 밑변이 가로 타일로만 이루어져 있으며, 양 끝은 세로 타일이 들어간다는 점이다. 이로 미루어 보아, $n$이 늘어날 때마다 유니크한 단위 타일이 2개씩 늘어남을 알 수 있다. 꼭 2개씩만 늘어나는 것인가 의문이 들 수 있는데, 색칠한 부분의 타일이 하나라도 세로로 놓이게 되면 이전 경우와 무조건 겹치게 된다. 세로로 놓인 부분이 $n=2$인 경우의 단위 타일과 겹치기 때문이다.

위 케이스들을 통해, 점화식을 도출해보자. $n>2$인 경우에 대해 아래 수식이 성립한다.

$${\displaystyle dp[n]=dp[n-2]\ast dp[2]+\sum _{i=4}^{n-2}(2\ast dp[n-i])+2}$$

$i$는 짝수이며, 맨 마지막 $+2$는 새로 추가되는 유니크한 단위 타일에 대한 경우의 수이다. dp[0] = 1 로 초깃값을 두어 유니크한 단위 타일에 대한 경우의 수 계산을 간단히 할 수 있다. dp[2] = 3이므로, 아래와 같이 코드를 작성하면 통과할 수 있다.

def solution(n):
    INF = 1_000_000_007
    dp = [0] * 5001
    dp[0] = 1
    dp[2] = 3
    for i in range(4, n + 1, 2):
        dp[i] = (dp[i - 2] * 3)
        for j in range(i - 4, -1, -2):
            dp[i] += (dp[j] * 2)
    return dp[n] % INF

프로그래머스 시간 제한이 넉넉해서 위 코드로도 충분히 통과할 수 있지만, 위 코드는 $O(N^2)$로 실제로 돌려보면 굉장히 느리다. 점화식을 정리하여 $O(N)$ 으로 최적화 할 수 있다.

점화식의 $+2$ 부분을 시그마로 합치면, 아래 수식이 된다.

$${\displaystyle dp[n]=dp[n-2]\ast 3+\sum _{i=4}^n(2\ast dp[n-i])}$$

위 수식으로 부터, 양변에서 $dp[n-2]$를 빼주면,

$${\displaystyle dp[n]-dp[n-2]=dp[n-2]\ast 2+\sum _{i=4}^n(2\ast dp[n-i])}$$

$${\displaystyle dp[n]-dp[n-2]=\sum _{i=4}^n(2\ast dp[n-i])}$$

이므로, 위 수식으로 점화식의 우항을 정리할 수 있으며, 최종 점화식은 다음과 같다.

$${\displaystyle dp[n]=4\ast dp[n-2]-dp[n-4]}$$

코드Permalink

def solution(n):
    INF = 1_000_000_007
    dp = [0] * 5001
    dp[0] = 1
    dp[2] = 3
    for i in range(4, n + 1, 2):
        dp[i] = (dp[i - 2] * 4 - dp[i - 4]) % INF 
    return dp[n]