C++ Coding Test Course, 2 N Tile Filling

Problem Description

The 2*N tile filling problem is to find the number of ways to fill a given 2xN space with 1×2 tiles.
Tiles can be placed either horizontally or vertically, and the entire 2xN space must be completely filled.
The key to this problem is calculating the number of combinations, which can be solved using Dynamic Programming techniques.

Input Format

An integer N is given. (1 ≤ N ≤ 30)

Output Format

Output the number of ways to fill the 2xN space as an integer.

Problem Solving Process

To solve the 2*N tile filling problem, we need to find the pattern of the problem through several examples.
First, let’s consider the cases when N is 1 and when N is 2.

Example

• N = 1:
  • 1 way: Place 1 tile vertically
• N = 2:
  • 2 ways: Place 2 tiles horizontally or place 2 tiles vertically

Here, we can discover the following pattern.
As N increases, each case can be divided as follows.

– If we place a tile horizontally in the Nth position, N-1 positions remain.
– If we place a tile vertically in the Nth position, N-2 positions remain.

Therefore, the recurrence relation can be expressed as:

                dp[n] = dp[n-1] + dp[n-2]
            

When setting this recurrence relation, we need to establish initial values.
dp[1] = 1 (1×2 tile placed vertically), dp[2] = 2 (either 2 horizontal tiles or 2 vertical tiles) is established.

Now, let’s write a C++ program to calculate the number of ways based on this recurrence relation by taking N as input.

C++ Code Implementation

                
                #include 
                using namespace std;

                int main() {
                    int N;
                    cin >> N;

                    int dp[31] = {0};
                    dp[1] = 1;
                    dp[2] = 2;

                    for (int i = 3; i <= N; ++i) {
                        dp[i] = dp[i - 1] + dp[i - 2];
                    }

                    cout << dp[N] << endl;
                    return 0;
                }
                
            

The code above creates a dp array for the given N and uses dynamic programming techniques to calculate the number of ways for each case.
Finally, it outputs dp[N] to determine the number of ways to fill the 2xN space with tiles.

Time Complexity

The time complexity of this algorithm is O(N).
This is because the for loop runs N times.
The space complexity is also O(N) due to the use of the dp array.

Conclusion

The 2*N tile filling problem is a typical example of dynamic programming.
The key is to break the problem down into smaller parts to create a recurrence relation that can be solved recursively.
As this problem is frequently encountered in coding tests, it is important to understand and practice it repeatedly.