문제
4×N 크기의 사각형을 2×1 의 크기의 타일로 빈칸 없이 채우고자 한다.
타일끼리 겹치는 경우는 불가능 하며, 빈칸 없이 채울 수 있는 경우의 수가 모두 몇 가지 인지 알아보는 프로그램을 작성하자.
경우의 수가 많아 질 경우를 대비 해 답은 100,000으로 나눴을 경우의 나머지에 대한 결과를 출력한다.
입력
입력은 여러 줄이 들어오며 각 줄마다 채우려는 사각형의 너비에 대한 숫자 N(N≤109)가 입력 된다.
0을 입력 받으면 입력을 종료한다.
출력
각 줄에 대해서 가능한 모든 경우의 수를 출력하되 이는 100,000으로 나눈 나머지로 출력을 한다.
입력된 줄은 처리하지 않는다.
예제
1
3
5
0
1
11
95
출처
poj 3420
로그인해야 코드를 작성할 수 있어요.