[코딩 인터뷰][HackerRank] Lego Blocks

※ 이 포스트는 HackerRank 문제인 Lego Blocks 해설을 담고 있습니다.
본 풀이는 Optimal하지 않을 수 있으며, HackerRank에서의 Submission 통과만을 보장합니다.

Lego Blocks

문제 출처 : https://www.hackerrank.com/challenges/lego-blocks/problem
카테고리 : DP
난이도 : Medium (50 point)

문제 설명

가로, 세로, 높이를 가진 직육면체가 4종류 있다. 높이와 세로는 모두 1로 동일하고 가로만 1, 2, 3, 4로 4종류가 있다. 이 블럭을 쌓아서 직육면체 벽을 세우려고 한다. 벽의 세로 길이는 1이라고 한다. 따라서 그냥 벽을 입체가 아니라 면이라고 생각하는게 더 편할 것 같다.

위와 같이 좋은 레이아웃과 나쁜 레이아웃을 구분짓는 기준은 하나다. 오른쪽 Bad layout과 같이 세로로 벽을 완전히 자를 수 있는 직선이 존재한다면 나쁜 레이아웃이다. 즉, 이어진 세로선이 벽의 세로길이와 완전히 같은 것을 나쁘다고 생각하면 된다.

만들어야 할 벽의 세로, 가로 (N, M)이 주어질 때 만들 수 있는 좋은 레이아웃의 수를 구하여라. 수가 너무 크다면 10^9 + 7로 나눈 나머지를 구하여라.

문제 풀이

우선 레이아웃의 좋고 나쁨을 구별하지말고, 벽을 구성할 수 있는 전체 가짓수를 알아보자. 한 줄을 완성하는 가짓수를 X라고 한다면, N개의 줄은 높이마다 독립적이므로 X^N이 정답이다.

block[i]를 i + 1칸짜리 한 줄을 만드는 경우의 수라고 하자. block[i]는 어떻게 만들어지는가. block[i – 4]에서 4칸짜리 블록을 추가하거나, block[i – 3]에서 3칸짜리 블록을 추가하거나하는 식이다. 즉, block[i] = block[i – 4] + block[i – 3] + block[i – 2] + block[i – 1] 이다. 물론 i – 4나 i – 3같은 값은 음수가 되어선 안된다.

block[i]별로 block[i]^N을 구한다. N을 2진수로 생각해서 곱하는 전략을 취한다. 예를 들어 3^5는 3^(1+0+4)와 같고, 3^13은 3^(1+0+4+8)과 같다. 13은 2진수로 1101이다. 매 Iteration마다 N을 2로 나눈 나머지가 1이면, 현재의 factor를 곱한다. factor는 매 Iteration마다 자기 자신의 제곱이된다.

이 과정을 거친 후 block[i]는 (N, i + 1)의 크기의 벽을 완성할 수 있는 경우의 수가 된다.

이제 이 중에서 나쁜 레이아웃을 제거함으로써, 좋은 레이아웃의 수만 남길 것이다. 나쁜 레이아웃을 최초로 세로로 잘리는 지점을 가지고 분류한다고 생각해보자. 만약 가로가 4칸인 벽이라고 한다면, 최초로 잘리는 지점이 1또는 2또는 3번째 칸일 것이다. 그렇다면, 잘리는 세로를 기준으로 왼쪽은 반드시 좋은 레이아웃 (그렇지 않다면, 그 지점보다 왼쪽에 세로로 잘리는 지점이 있다는 말이므로 가정에 위배된다.)이고 오른쪽은 아무 레이아웃이나 있으면 된다.

가로가 i + 1인 벽의 좋은 레이아웃의 수를 ans[i]라고 하자.

ans[3] = block[3] (전체 가능한 레이아웃 수) – ans[0] * block[2] – ans[1] * block[1] – ans[2] * block[0] 이다.

코드

#!/bin/python3

import os
import sys

#
# Complete the legoBlocks function below.
#
def legoBlocks(n, m):
    #
    # Write your code here.
    #
    mod = 10 ** 9 + 7
    block = [0] * m
    
    for i in range(min(m, 4)):
        block[i] = 1

    for i in range(m):
        for j in range(1, 5):
            if i + j < m:
                block[i + j] = (block[i + j] + block[i]) % mod
        x = n
        tmp = block[i]
        block[i] = 1
        while x > 0:
            if x % 2 == 1:
                block[i] = (block[i] * tmp) % mod
            tmp = (tmp * tmp) % mod
            x //= 2

    ans = [0] * m
    for i in range(m):
        ans[i] = block[i]
        for j in range(i):
            ans[i] = (ans[i] - ans[j] * block[i - 1 - j]) % mod
    return (ans[m - 1] + mod) % mod
        
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        nm = input().split()

        n = int(nm[0])

        m = int(nm[1])

        result = legoBlocks(n, m)

        fptr.write(str(result) + '\n')

    fptr.close()

코딩 인터뷰 – Lego Blocks