문제
3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.
힌트
아래 그림은 3×12 벽을 타일로 채운 예시이다.
W3sicHJvYmxlbV9pZCI6IjIxMzMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWQwYzBcdWM3N2MgXHVjYzQ0XHVjNmIwXHVhZTMwIiwiZGVzY3JpcHRpb24iOiI8cD4zJnRpbWVzO04gXHVkMDZjXHVhZTMwXHVjNzU4IFx1YmNiZFx1Yzc0NCAyJnRpbWVzOzEsIDEmdGltZXM7MiBcdWQwNmNcdWFlMzBcdWM3NTggXHVkMGMwXHVjNzdjXHViODVjIFx1Y2M0NFx1YzZiMFx1YjI5NCBcdWFjYmRcdWM2YjBcdWM3NTggXHVjMjE4XHViOTdjJm5ic3A7XHVhZDZjXHVkNTc0XHViY2Y0XHVjNzkwLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBOKDEgJmxlOyBOICZsZTsgMzApXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YWNiZFx1YzZiMFx1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIDMmdGltZXM7MTIgXHViY2JkXHVjNzQ0IFx1ZDBjMFx1Yzc3Y1x1Yjg1YyBcdWNjNDRcdWM2YjQgXHVjNjA4XHVjMmRjXHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cImh0dHBzOlwvXC9vbmxpbmVqdWRnZWltYWdlcy5zMy1hcC1ub3J0aGVhc3QtMS5hbWF6b25hd3MuY29tXC91cGxvYWRcL2ltYWdlc1wvMjY2M18xLmpwZ1wiIHN0eWxlPVwiaGVpZ2h0OjgwcHg7IHdpZHRoOjI3M3B4XCIgXC8+PFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiIyMTMzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiVHJpIFRpbGluZyIsImRlc2NyaXB0aW9uIjoiPHA+SW4gaG93IG1hbnkgd2F5cyBjYW4geW91IHRpbGUgYSAzeG4gcmVjdGFuZ2xlIHdpdGggMngxIGRvbWlub2VzPzxcL3A+XHJcblxyXG48cD5IZXJlIGlzIGEgc2FtcGxlIHRpbGluZyBvZiBhIDN4MTIgcmVjdGFuZ2xlPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5JbnB1dCBjb25zaXN0cyBvZiZuYnNwO2EgbGluZSBjb250YWluaW5nIGFuIGludGVnZXIgMCAmbGU7IG4gJmxlOyAzMC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgb25lIGludGVnZXIgbnVtYmVyIGdpdmluZyB0aGUgbnVtYmVyIG9mIHBvc3NpYmxlIHRpbGluZ3MuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==