[HackerRank] Lego Blocks

Problem

---

You have an infinite number of 4 types of lego blocks of sizes given as (depth x height x width):

d	h	w
1	1	1
1	1	2
1	1	3
1	1	4

Using these blocks, you want to make a wall of height n and width m. Features of the wall are:

- The wall should not have any holes in it.
- The wall you build should be one solid structure, so there should not be a straight vertical break across all rows of bricks.
- The bricks must be laid horizontally.

How many ways can the wall be built?

 

Example

n = 2

m = 3

The height is 2 and the width is 3. Here are some configurations:

These are not all of the valid permutations. There are 9 valid permutations in all.

 

Function Description

Complete the legoBlocks function in the editor below.

legoBlocks has the following parameter(s):

• int n: the height of the wall
• int m: the width of the wall

Returns
- int: the number of valid wall formations modulo (10^9 + 7)

Input Format

The first line contains the number of test cases t.

Each of the next t lines contains two space-separated integers n and m.

Constraints

1 ≤ t ≤ 100

1 ≤ n, m ≤ 1000

Sample Input

STDIN   Function
-----   --------
4       t = 4
2 2     n = 2, m = 2
3 2     n = 3, m = 2
2 3     n = 2, m = 3
4 4     n = 4, m = 4

Sample Output

3  
7  
9  
3375

Explanation

For the first case, we can have:

 

3 mod (10^9 + 7 ) = 3

For the second case, each row of the wall can contain either two blocks of width 1, or one block of width 2. However, the wall where all rows contain two blocks of width 1 is not a solid one as it can be divided vertically. Thus, the number of ways is 2*2*2-1 = 7 and 7 mod (10^9 + 7) = 7.

 

 

---

4가지 유형의 레고 블록이 있습니다. 각 블록의 크기는 아래와 같습니다.

깊이(d)	높이(h)	너비(w)
1	1	1
1	1	2
1	1	3
1	1	4

이 블록을 사용하여 높이가 n이고 너비가 m인 벽을 만들려고 합니다. 벽의 특징은 다음과 같습니다:

• 벽에는 구멍이 없어야 합니다.
• 하나의 고체 구조로 만들어져야 하며, 모든 행에 걸쳐 수직으로 완전히 단절되는 부분이 없어야 합니다.
• 벽돌은 가로로 놓아야 합니다.

이 조건을 만족하는 벽을 만들 수 있는 방법의 수를 구하세요.

 

예시

예를 들어, n = 2, m = 3인 경우를 고려해 봅시다. 높이가 2이고 너비가 3인 벽을 만들 수 있는 몇 가지 경우는 다음과 같습니다:

이와 같은 유효한 조합이 9개 존재합니다.

 

함수 설명

다음의 매개변수를 갖는 legoBlocks 함수를 작성하세요:

• int n: 벽의 높이
• int m: 벽의 너비

반환값

• int: 유효한 벽을 만들 수 있는 조합의 수를 (10^9 + 7)로 나눈 나머지 값

입력 형식

• 첫 줄에는 테스트 케이스의 수 t가 주어집니다.
• 다음 t개의 줄 각각에는 두 개의 정수 n과 m이 공백으로 구분되어 주어집니다.

제약 사항

• 1≤t≤1001 \leq t \leq 1001≤t≤100
• 1≤n,m≤10001 \leq n, m \leq 10001≤n,m≤1000

 

 

728x90

 

 

 

Solution

---

문제를 풀기 위해 재귀적 접근과 동적 프로그래밍을 사용하여 벽을 만드는 모든 가능한 방법을 계산하고, 각 높이와 너비에 대해 유효한 조합을 찾아 수직 분리 없이 벽을 만드는 방법을 찾습니다.

import java.util.Arrays;

public class Solution {

    public static int legoBlocks(int n, int m) {
        int MOD = 1_000_000_007;

        // 1. 각 열마다 가능한 모든 배치의 수를 계산합니다.
        int[] singleRowWays = new int[m + 1];
        singleRowWays[0] = 1;
        
        for (int i = 1; i <= m; i++) {
            singleRowWays[i] = singleRowWays[i - 1];
            if (i >= 2) singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 2]) % MOD;
            if (i >= 3) singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 3]) % MOD;
            if (i >= 4) singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 4]) % MOD;
        }

        // 2. n층까지 높이로 쌓을 수 있는 모든 벽의 수 계산
        int[] totalWays = new int[m + 1];
        for (int j = 1; j <= m; j++) {
            totalWays[j] = 1;
            for (int i = 1; i <= n; i++) {
                totalWays[j] = (int) ((long) totalWays[j] * singleRowWays[j] % MOD);
            }
        }

        // 3. 무효한 조합(수직으로 분리된 조합) 제외
        int[] solidWays = Arrays.copyOf(totalWays, m + 1);
        for (int width = 1; width <= m; width++) {
            for (int k = 1; k < width; k++) {
                solidWays[width] = (solidWays[width] - (int) ((long) solidWays[k] * totalWays[width - k] % MOD) + MOD) % MOD;
            }
        }

        return solidWays[m];
    }

    public static void main(String[] args) {
        System.out.println(legoBlocks(2, 2)); // Output: 3
        System.out.println(legoBlocks(3, 2)); // Output: 7
        System.out.println(legoBlocks(2, 3)); // Output: 9
        System.out.println(legoBlocks(4, 4)); // Output: 3375
    }
}

 

 

• singleRowWays 배열을 사용해 너비 m을 채우는 한 행의 모든 가능한 조합을 계산합니다.
• totalWays 배열은 높이 n까지의 모든 행에 대해 계산한 총 가능한 조합의 수를 저장합니다.
• solidWays 배열을 사용하여 수직으로 단절되지 않은 유효한 벽의 경우의 수를 구합니다.

---

public static int legoBlocks(int n, int m) {
    int MOD = 1_000_000_007;

MOD는 답이 매우 커질 수 있기 때문에 결과를 10^9 + 7로 나눈 나머지로 반환하기 위해 설정된 값입니다.

 

1. 각 열마다 가능한 모든 배치의 수를 계산

int[] singleRowWays = new int[m + 1];
singleRowWays[0] = 1;

 

• singleRowWays는 너비가 i일 때 한 줄에 블록을 배치할 수 있는 모든 가능한 조합의 수를 저장하는 배열입니다.
• singleRowWays[0] = 1로 초기화하여 너비가 0일 때는 하나의 방법(블록이 없는 경우)이 있다고 설정합니다.

for (int i = 1; i <= m; i++) {
    singleRowWays[i] = singleRowWays[i - 1];
    if (i >= 2) singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 2]) % MOD;
    if (i >= 3) singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 3]) % MOD;
    if (i >= 4) singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 4]) % MOD;
}

 

• 이 부분은 너비 i의 벽을 한 줄로 쌓을 수 있는 모든 조합을 계산하는 코드입니다.
• 각 식의 의미:
  • singleRowWays[i] = singleRowWays[i - 1]: 너비 i-1까지 놓은 상태에서 너비 1의 블록을 추가한 경우를 의미합니다.
  • singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 2]) % MOD: 너비 i-2까지 놓은 상태에서 너비 2의 블록을 추가한 경우를 추가합니다.
  • singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 3]) % MOD: 너비 i-3까지 놓은 상태에서 너비 3의 블록을 추가한 경우를 추가합니다.
  • singleRowWays[i] = (singleRowWays[i] + singleRowWays[i - 4]) % MOD: 너비 i-4까지 놓은 상태에서 너비 4의 블록을 추가한 경우를 추가합니다.
  • 이 반복문이 종료되면, singleRowWays[i]에는 각 열 너비 i에 대해 가능한 모든 블록 조합의 수가 저장됩니다.

 

2. n층 높이의 벽을 쌓을 수 있는 모든 조합 계산

int[] totalWays = new int[m + 1];
for (int i = 1; i <= m; i++) {
    totalWays[i] = 1;
    for (int j = 1; j <= n; j++) {
        totalWays[i] = (int) ((long) totalWays[i] * singleRowWays[i] % MOD);
    }
}

 

• totalWays[i]는 너비 i와 높이 n일 때 벽을 쌓는 모든 가능한 조합의 수를 저장하는 배열입니다.
• 각 식의 의미:
  • totalWays[i] = (int) ((long) totalWays[i] * singleRowWays[i] % MOD);
    • totalWays[i]를 n층만큼 singleRowWays[i]로 곱하여 총 가능한 모든 조합 수를 구합니다.
    • (long)을 사용하여 오버플로우를 방지하고, % MOD로 나머지 연산을 수행하여 값을 제한합니다.

 

3. 수직으로 나뉘는 벽의 조합을 제외하여 유효한 벽 조합 계산

int[] solidWays = Arrays.copyOf(totalWays, m + 1);

• Arrays.copyOf(totalWays, m + 1)는 totalWays 배열의 길이 m+1만큼의 복사본을 solidWays에 저장합니다.
• 여기서 solidWays[width]는 너비 width에서 모든 조합을 계산한 후 수직으로 나뉘지 않는 조합만 남긴 값이 됩니다.

for (int width = 1; width <= m; width++) {
    for (int k = 1; k < width; k++) {
        solidWays[width] = (solidWays[width] - (int) ((long) solidWays[k] * totalWays[width - k] % MOD) + MOD) % MOD;
    }
}

• 이 부분에서는 solidWays[width]에서 수직으로 나뉘는 벽의 조합을 빼서 수직 분리가 없는 경우만 남깁니다.
• 각 식의 의미:
  • (solidWays[width] - (int) ((long) solidWays[k] * totalWays[width - k] % MOD) + MOD) % MOD;
    • solidWays[k] * totalWays[width - k]는 너비 k의 벽이 고정되고 나머지 너비 width - k가 다른 조합으로 나뉘어 수직 분리가 발생하는 경우를 계산합니다.
    • MOD로 나머지 연산을 통해 음수 값이 나오지 않도록 합니다.

 

4. 반환값

return solidWays[m];

 

solidWays[m]는 높이 n, 너비 m에서 수직으로 나뉘지 않은 조합의 최종 개수입니다.