백준: 11726 2xn 타일링

문제

11726번: 2×n 타일링

 

문제 풀이

세로 타일(2 x 1)과 가로 타일(1 x 2) 타일로 n이 입력될 경우 타일을 붙일 수 있는 경우의 수를 구하는 문제이다. n에 따라 발생할 수 있는 각 경우의 수는 크게 3가지 이다.

 

1. 모두 세로 타일로 구성 되는 경우
2. 모두 가로 타일로 구성 되는 경우
3. 가로, 세로 타일이 혼합되어 구성되는 경우

Figure 1. n에 따른 타일을 붙일 수 있는 경우의 수

 타일을 붙일 수 있는 경우의 수는 그림 1과 같다. n에 따른 규칙을 찾아보면 n이 증가함에 따라 1, 2, 3, 5, 8, 13로 증가하는 것을 알 수 있다. 이를 식으로 나타내면 `f(n) = f(n - 1) + f(n - 2)`가 된다. 즉, 피보나치 수열을 구하는 것과 같다.

 

풀이

from sys import stdin


if __name__ == "__main__":
    n = int(stdin.readline())
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    print(a % 10007)

 규칙을 찾는 과정은 나열하고 생각해보아야 하지만, 코드는 아주 간단하다.😉