[백준] 11726 | 2xn 타일링 [파이썬/python]

문제

link: https://www.acmicpc.net/problem/11726

2xn 크기 직사각형을 1x2, 2x1 크기 타일로 채우는 경우의 수를 구해 10007로 나누었을 때의 나머지를 출력하는 문제이다.

 

접근

%10007을 출력해야 한다는 사실을 꼭 유념해야 한다!(중요해서 위에 씀)

 

전에 푼 백준 9095번 문제와 비슷하다고 느꼈다. (https://going-on.tistory.com/43) 동일하게 이전 항의 값을 이용해 n일 때의 값을 구할 수 있다.

[백준] 9095 | 1, 2, 3 더하기 [파이썬/python]

2xn 크기 직사각형을 타일로 채우기 위한 두 가지 방법을 떠올릴 수 있다.

1. 2x(n-1) 크기 직사각형의 끝에 2x1 타일을 붙인다.

2. 2x(n-2) 크기 직사각형의 끝네 1x2 타일(두 개)을 붙인다.

따라서, f(n) = f(n-1) + f(n-2)에 맞추어 코드를 구현했다.

 

사실 n일 때의 값을 나열해 보기만 해도 쉽게 답을 유추할 수 있다. 피보나치 수열은 이제 너무 익숙해서...😅

 

수식으로도 접근할 수 있다. 1x2 타일 개수를 늘려가면서, 미리 나열해 둔 2x1 타일 사이에 1x2 타일을 끼워넣는 경우의 수를 구해 더하면 된다. 중복조합을 사용하여 구할 수 있다.

결과적으로 2xn 타일을 채우는 경우의 수는 nC0 + (n-1)C1 + ... + (n-k)Ck (k가 0에서 n//2일 때까지) 와 같다. 사실 나는 이 방법을 먼저 떠올렸지만, 처음 언급한 방식이 구현하기 쉽고 효율성도 좋으므로 이것을 코드로 구현하지는 않았다.

 

코드

import sys
input = sys.stdin.readline

n = int(input())

a = [0, 1, 2] + [0]*(0 if n < 3 else n - 2)

for i in range(3, n + 1):
    a[i] = (a[i-1] + a[i-2]) % 10007

print(a[n])

%10007 연산은 for문 안에서 하는 것이 좋다.(리스트에 저장되는 값 크기가 줄어들어 효율적이다.)