[Algorithm] 프로그래머스 - 아방가르드 타일링

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

접근

여러 경우의 수를 고려해야 하는 DP 문제다.

규칙성을 찾기 위해서는 $n$ 이 증가함에 따라 새로 추가되는 영역을 봐야 한다.

일단 문제에서도 확인할 수 있듯이 $n=3$ 인 경우의 수는 10이다.

여기서 $n=4$ 에서 재사용할 수 있는 경우는 90도 회전된 $3\times{1}$ 타일이 있는 경우다.

나머지 $3\times{1}$ 타일이 있는 경우는 $n=1$ 에서의 결과를 재사용하고, ㄱ자 타일로만 구성된 $3\times{2}$ 타일에서는 $n=2$ 에서의 결과를 재사용해야 하기 때문이다.

다음으로 $n=4$ 에서 재사용 가능한 경우는 다음과 같이 두 개다.

90도 회전된 $3\times{1}$ 타일로 가로를 꽉 채우도록 타일링하는 데 초점을 두면 이러한 경우를 쉽게 찾을 수 있다.

$n=5$ 일 때는 다음과 같이 두 개다.

$n=6$ 일 때는 다음과 같이 네 개다.

$n=7$ 일 때는 다음과 같이 두 개다.

다음은 $n=8$ 일 때와 $n=9$ 일 때의 경우 중 한 개씩만 나타낸 그림이다.

한 개씩만 나타낸 이유를 설명하겠다.

눈치챘을 수도 있을 것이다. $n$ 이 7 이상일 때부터는 90도 회전된 $3\times{1}$ 타일 세 개가 연속으로 쌓아진 형태가 계속 추가되기 때문에 비슷한 형태가 반복된다.

예를 들어 다음과 같이 $n=7$ 일 때의 하나의 경우는 $n=4$ 일 때의 경우에서 90도 회전된 $3\times{1}$ 타일 세 개가 연속으로 쌓아진 형태가 추가되는 식이다.

$n=8$ 과 $n=9$ 일 때도 마찬가지다.

그래서 점화식은 다음과 같이 세울 수 있다.

$dp[i]=dp[i-1]+2\times{dp[i-2]}+5\times{dp[i-3]}+2\times{dp[i-4]}+2\times{dp[i-5]}+4\times{dp[i-6]}+2\times{dp[i-7]}+2\times{dp[i-8]}+4\times{dp[i-9]}...$

이를 구현하기 위해서는 누적합을 저장해서 계산해도 되지만 다음과 같이 식을 간소화할 수도 있다.

$dp[i] - dp[i-3] = dp[i-1]+2\times{dp[i-2]}+5\times{dp[i-3]}+dp[i-4]-dp[i-6]$

$dp[i] = dp[i-1]+2\times{dp[i-2]}+6\times{dp[i-3]}+dp[i-4]-dp[i-6]$

그리고 문제에서 나머지 연산을 필요로 하는데,

자바에서는 뺄셈에서 모듈러 연산 시 음수를 배제하기 위해 다음 식을 적용한다.

$(A-B)\mod{M}=((A\mod{M})-(B\mod{M})+B)\mod{M}$

이와 관련해 포스팅을 한 적이 있다. 궁금하면 다음 글을 참고하자.

https://tenutz.tistory.com/51

소스코드(Java)

class Solution {

    static final int MOD = 1000000007;

    public long solution(int n) {
        long[] dp = new long[100001];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 3;
        dp[3] = 10;

        dp[4] = 23;
        dp[5] = 62;
        dp[6] = 170;

        //dp[12] = dp[11] + 2*dp[10] + 5*dp[9] + 2*(dp[8]+dp[5]+dp[2]) + 2*(dp[7]+dp[4]+dp[1]) + 4*(dp[6]+dp[3]+dp[0]);
        //dp[9] = dp[8] + 2*dp[7] + 5*dp[6] + 2*(dp[5]+dp[2]) + 2*(dp[4]+dp[1]) + 4*(dp[3]+dp[0]);
        //dp[12] - dp[9] = dp[11] + 2*dp[10] + 5*dp[9] + dp[8] - dp[6];
        //dp[12] = dp[11] + 2*dp[10] + 6*dp[9] + dp[8] - dp[6];
        for(int i = 7; i <= n; i++) {
            dp[i] = (dp[i-1] + (2*dp[i-2]) % MOD + (6*dp[i-3]) % MOD + dp[i-4] - dp[i-6] + MOD) % MOD;
        }
        return (int)dp[n] % MOD;
    }
}