[백준/Python] 11726 : 2xn 타일링

 

2xn 크기 직사각형을 채우는 방법의 수를 구하는 문제이기 때문에 숫자가 매우 커지게 되므로 10007로 나눈 나머지를 출력해야 한다.

피보나치 수열과 비슷한 구조로 해결할 수 있는데, 이 타일링 방법의 규칙을 분석해보면 다음과 같다.

 

 

f(n) = f(n-1) + f(n-2)

 

f(n-1) : 2x1 크기의 타일을 세로로 하나 추가한 경우

f(n-2) : 1x2 크기의 타일을 두 개 추가한 경우 

 

최소가 n-2 이기 때문에 각각 f(1)과 f(2)의 초깃값을 부여해야 한다.

2x1 직사각형을 채우는 방법은 1가지 이므로 f(1) = 1 , 2x2 직사각형을 채우는 방법은 2가지 이므로 f(2) = 2 이다.

 

따라서 최종적으로 결과는 f(n) % 10007 인 셈!

 

++ 여기서 굳이 다른 숫자도 아니고 10007 숫자를 이용하는 이유는 물론 문제에서 제시했기 때문도 있지만, 바로 10007가 매우 큰 소수 중 하나로 모듈러 연산의 성질이 좋고, 계산 중간의 숫자를 균등하게 분포시키는 효과가 있어 결과값이 무작위로 커지는 것을 방지하는 데 도움을 주는 숫자이기 때문이라고 한다!

 

n = int(input())

# 다이나믹 프로그래밍 테이블 초기화
dp = [0] * (n+1)
dp[1] = 1
if n > 1: dp[2] = 2

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

print(dp[n])

 

- 먼저 n을 입력 받고 f(0)부터 사용하기 위해 dp 배열 크기를 (n+1)로 초기화하고 dp[1]과 dp[2] 값을 설정해준다.

- 이후 앞서 구해놨던 점화식을 계산하도록 for 루프에서 3부터 n까지 해당 식을 구현하여 dp[i] 값을 계산한다.

(이때 10007 을 나누며 값이 커지지 않도록 제한함)

- 최종적으로 dp[n]을 출력하여 2xn 크기 직사각형을 채우는 방법의 수를 구해준다.