Forum

Post 19.05.2009   # 1
Subject CodeFu 2009 Round 2 - Problem 400
400. Board Covering

This problem can be easily solved using dynamic programming. Lets examine what are our options when covering the board with tiles. When we are about to put the first tile, we can either:

[list]1. Put the first tile vertically in the first column. This way the first column is totally covered, and we are left with a board of length N-1.[/list]
[list]2. Put the first tile horizontally (covering the bottom row of the first three columns of the board). In order to leave no gaps in the cells that are above this first tile, we must put two additional horizontal tiles. This way, the first three columns are covered and we are left with a board of length N-3.[/list]

So, we have the following recurrent formula: f(N) = f(N-1) + f(N-3).

public class BoardCovering {
public int count(int N) {
int[] a = new int[1000001];
a[0]=1; a[1]=1; a[2]=1;
for (int i = 3; i <= N; ++i) {
a[i] = a[i - 1] + a[i - 3];
a[i] %= 1000007;
}
return a[N];
}
}
bilievsk is offline Reply

Please login to post reply.