[Programmers] 아방가르드 타일링

Computer Science | 2024-03-26

프로그래머스 스킬체크에서 레벨3 코딩테스트를 해봤다.

앞으로 알고리즘 문제를 풀기 위해 내 능력을 한 번 점검해봤다. 첫 문제로는 표 병합이 나왔고(22.7점밖에 안나왔다…), 다음 문제로 아방가르드 타일링를 풀었다. 이 문제도 시간 내에는 풀지 못했지만, 다시 풀어본 내용을 정리하려고 한다.

1. 문제

문제는 n × 3의 벽을 위와 같은 모양의 타일을 이용해서 채우는 방법의 수를 구하는 문제이다. 자신보다 더 짧은 벽을 채우는 방법의 수와 관련이 있으므로 DP로 풀이할 수 있다.

2. 풀이

n × 3의 벽을 채우는 경우의 수를 $a_n$ 이라고 하면, $a_1 = 1$, $a_2 = 3$, $a_3 = 10$이 된다. n = 1일 때 새롭게 생기는 패턴이 1가지, n = 2일 때는 2가지, n = 3일 때는 5가지이다. 이는 문제에서 그림을 제공했기 때문에 빠르게 파악할 수 있다. 이제 n = 4일 때를 생각해보면, 이 때 새로 생기는 패턴은 다음의 2가지가 된다.

똑같은 방식으로, n = 5일 때와 n = 6일 때를 생각해보면,

로 각각 2가지, 4가지이다. n = 7, n = 8, n = 9일 떄는 n = 4, n = 5, n = 6인 경우 각각에 보라색 블럭이 하나씩 들어간 모양일 것이므로 똑같이 2, 2, 4가지가 추가될 것이다. 따라서 DP를 위한 식은 다음과 같이 쓸 수 있다.

$$ a_n = a_{n-1}+ 2a_{n-2} + 5a_{n-3} + 2a_{n-4} + 2a_{n-5} + 4a_{n-6} + \cdots $$

처음에는 이를 다음과 같이 구현했다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
long long dp[100001] = {1, 1, 3, 10, 23, 62, 170,};

int mod = 1000000007;

int solution(int n) {
    for (int i = 7; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + (2 * dp[i - 2]) + (5 * dp[i - 3])) % mod;

        for (int j = 4; j <= i; j++)
        {
            if (j % 3 == 0)
                dp[i] += dp[i - j] * 4;
            else
                dp[i] += dp[i - j] * 2;
        }
        dp[i] %= mod;
    }
    return dp[n];
}

이렇게 해도 문제를 통과하는데는 문제가 없다. 하지만 마지막 몇 개의 케이스에서 5초 정도 걸렸다. 이렇게 구현하면 $O(n^2)$ 이 되는데, 이 문제는 사실 $O(n)$으로 풀이가 가능하다. 누적합을 이용하면 되는데, 다음과 같다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
long long dp[100001] = {1, 1, 3, 10, 23, 62, 170,};
long long sum[1000001] = {1, 1, 3, 11, 24, 65, 181, };

int mod = 1000000007;

int solution(int n) {
    for (int i = 7; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + (2 * dp[i - 2]) + (5 * dp[i - 3])) % mod;
        dp[i] = (dp[i] + (sum[i - 4] * 2) + \
                 (sum[i - 5] * 2) + (sum[i - 6] * 4)) % mod;

        sum[i] = sum[i - 3] + dp[i];
        sum[i] %= mod;
    }
    return dp[n];
}

그리고 이 코드를 리뷰하면서 찾아본 결과, 조금 더 수학적으로 접근해서 공간도 절약하는 풀이를 발견했다. 위에서 구한 $a_n$과, $a_{n-3}$을 식으로 나타내면,

equation_light

이고, 위에서 아래를 뺴면 다음을 얻을 수 있다.

$$ a_n = a_{n-1}+ 2a_{n-2} + 6a_{n-3} + a_{n-4} - a_{n-6} $$

이를 코드로 구현하면 다음과 같다.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <string>
#include <vector>
#include <iostream>
using namespace std;

long long dp[100001] = {1, 1, 3, 10, 23, 62, };

int mod = 1000000007;

int solution(int n) {
    for (int i = 6; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + 2 * dp[i - 2] + 6 * dp[i - 3] + \
                 dp[i - 4] - dp[i - 6] + mod) % mod;
    }
    return dp[n];
}

dp배열에 담겨있는 값은 mod로 나머지연산을 한 이후의 값이므로 dp[i - 6]을 빼게 되면 값이 음수가 될 수 있다. 따라서 mod를 한 번 더한 뒤에 나머지연산을 해준다.

3. 느낀 점

학교 과제와 시험으로 간단한 dp를 구현해 봤지만 코딩환경에서 구현하는 것은 느낌이 조금 달랐다. 또한 점화식을 쓴 뒤에 그 규칙성을 파악해서 수학적으로 조금 더 단순화 할 수 있다는 것을 알게 되었다. 코딩테스트 문제는 수학적으로 접근한다는 생각을 잘 안하고 있었는데 수학적인 접근도 충분히 한 뒤에 코드로 구현하면 더 빠르고 좋은 코드를 쓸 수 있을 것 같다.

#Algorithm #DP