Checkmate (aka the urinal problem) My Precalc teacher has one of his favorite problems that he made up (or more likely stole inspired by xkcd) that involves a row of n urinals. "Checkmate" is a situation in which every urinal is already occupied OR has an occupied urinal next to them. For instance, if a person is an X, then

X-X--X

is considered checkmate. Note that a person cannot occupy a urinal next to an already occupied urinal.

Task

Your program will take a number through stdin, command line args, or a function argument. Your program will then print out or return the number of ways that checkmate can occur in with the inputted number of urinals.

Examples

0 -&gt; 1 (the null case counts as checkmate)
1 -&gt; 1 (X)
2 -&gt; 2 (X- or -X)
3 -&gt; 2 (X-X or -X-)
4 -&gt; 3 (X-X-, -X-X, or X--X)
5 -&gt; 4 (X-X-X, X--X-, -X-X-, or -X--X)
6 -&gt; 5 (X-X-X-, X--X-X, X-X--X, -X--X- or -X-X-X)
7 -&gt; 7 (X-X-X-X, X--X-X-, -X-X--X, -X--X-X, X-X--X-, X--X--X or -X-X-X-)
8 -&gt; 9 (-X--X--X, -X--X-X-, -X-X--X-, -X-X-X-X, X--X--X-, X--X-X-X, X-X--X-X, X-X-X--X, X-X-X-X-)
...

Scoring

The smallest program in bytes wins.
Oasis, 5 bytes

Code

cd+2V


Extended version

cd+211


Explanation

1 = a(0)
1 = a(1)
2 = a(2)

a(n) = cd+
       c      # Calculate a(n - 2)
        d     # Calculate a(n - 3)
         +    # Add them up


Try it online!