[Gold II] 4×n 타일링 - 11333

문제 링크

성능 요약

메모리: 31256 KB, 시간: 52 ms

분류

다이나믹 프로그래밍

문제 설명

icpc 왕국에는 아주 못된 왕 유빈이가 있었다.

유빈이에게는 4×n 크키의 카펫이 하나 있었다.

유빈이는 신하들에게 이 카펫을 3×1 타일과 1×3 타일로 빈틈없이 메우라는 명령을 내렸다.

여러분이 신하들을 도와서 4×n 크기의 카펫을 3×1 타일과 1×3 타일로 메우는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 테스트 케이스의 수 T가 주어진다. (1 <= T <= 100)

그 다음 T개의 줄에는 카펫에 가로 길이 N이 주어진다. (세로 길이는 4) (1 <= N <= 10,000)

출력

각 테스트 케이스마다 문제의 정답을 1,000,000,007로 나눈 나머지를 출력한다.

---

풀이

아이디어

어쩌다보니 회고에 모든 내용을 썼으므로, 경우의 수를 찾는 과정만 따라간다.

타일이 $1\times3$, $3\times1$이고, 채워야 할 판은 $4\times n$이므로, 3의 배수가 아닌 경우에는 판을 채울 수 있는 경우의 수가 없으므로 모두 0이다.

$n=3$
이 경우는 간단히 손으로 직접 세어봤을때 3가지 경우의 수가 나오므로 3이다.

$n=6$
$n=3$이 2개 붙어있는 모양이며, 그 이외의 경우의 수를 더해주어야 한다.
따라서 계산식은 $(2\times2) + 3^2$이다. 아래 그림은 $n=3$에 포함되지 않는 것들의 경우의 수이다.

이 과정을 따라가다보면 회고에 있는 블로그와 같은 수식이 나오는데, 이 규칙을 이용하여 수식을 최적화 한 뒤 점화식을 작성하였다.

종만북에서 Top-Down 방식을 고수하였으므로 (가독성 등의 이유)그렇게 풀이하려 했으나, 도저히 내 대가리로는 생각이 나지 않아서 결국 Bottom-Up 방식을 사용하기로 하였다.

코드

MOD = 1000000007
def solve(ans):
    n = int(input())
    if n == 0:
        return 1
    if n % 3 != 0:
        return 0
    
    return ans[n // 3]


if __name__ == "__main__":
    ans = [1, 3, 13]
    for i in range(3, 10000, 1):
        k = (((5 * ans[i-1]) % MOD) + MOD - ((3 * ans[i-2]) % MOD) + ans[i-3])% MOD
        ans.append(k)
    
    for i in range(int(input())):
        print(solve(ans))

---

회고

정말 어려웠던 문제이다. 3일을 꼬박 생각했고, 도구의 힘을 빌려 겨우 점화식을 만들어냈다. 이번 문제를 통해 새로 알아낸 것은 "Mutual Recursion"으로, Bottom Up 방식으로 풀이한 이 문제를 누군가는 위 기법을 사용해 Top-Down 으로 풀이했다는 것이 놀라웠다, (3개의 상호재귀를 이용하면 된다는데,, 고민해봐야겠다.)

또한 손으로 풀어나가면서 점화식을 만드는과정은 블로그를 참고했다. 참고하고나서도 한참 들여다봤던 문제..

이를 최적화 한 사이트는 이 사이트이다. 끝까지 해내고 싶었는데, 이 문제를 더이상 잡고 있는것은 시간낭비라 판단하여 도구를 사용하였고, 사실상 풀었다기보다는 배꼈다가 맞는 표현이라 조금 찝찝한 문제이다.

얻은게 없는게 아닌지라, 수학적 사고력을 조금 더 키우고, 경험을 늘리면 이런 비슷한 문제를 풀 수 있을 것이라고 생각한다.