BOJ 백준온라인져지 2133 타일 채우기 풀이

문제 설명 및 풀이

1. 3 * 2 일 때 만들 수 있는 경우 3 가지

2. 3 * 4 부터 2 * 2 를 추가할 수 있다. 그래서 2 가지 더해주고

3. 3 * 6 일 때 또 패턴 생기고 쭉 생김

증명

솔직히 증명은 못하겠다. (다른 블로그들을 참고했기 때문이다.)

1. 비트마스크로 구하고 DP 하는 방법도 있다한다. 그건 증명이 가능할듯

코드

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 

2

예제 출력 1 

3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

출처

Contest > Waterloo's local Programming Contests > 24 September, 2005 D번