[백준 13976번] 타일 채우기 2 (Python3)

import sys
input = sys.stdin.readline
mod = 1000000007

def multiply(A1,A2):
  result = [[0,0],[0,0]]
  for i in range(2):
    for j in range(2):
      for k in range(2):
        result[i][j] += A1[i][k]*A2[k][j]
        result[i][j] %= mod
  return result

def cal(A,n):
  if n == 1:
    return A
  cal2 = cal(A,n//2)
  result = multiply(cal2,cal2)
  if n%2:
    return multiply(result,A)
  return result

N = int(input())
if N%2:
  print(0)
else:
  N //= 2
  A = [[4,-1],[1,0]]
  print(sum(cal(A,N)[0])%mod)

#[0,0,3,0,11,0,41,0,153,0,571,0,2131,0,7953,0,29681,0,110771,0,413403,0,1542841,0,5757961,0,21489003,0,80198051,0,299303201]

 

엄청 쉽게 풀었는데, 증명은 못하겠는 문제

 

타일 채우기 1 문제 [백준 2133번] 타일 채우기 (Python3) (tistory.com) 에서 1~30까지의 값을 저장해놨었는데, 이걸 읽다보니까 점화식이 바로 보였다.

N이 짝수인 경우 n = N//2에 대해서 a[n] = 4*a[n-1] - a[n-2] 라는 것이다.

 

점화식이 바로 보였기 때문에 문제 푸는건 매우 수월했다.

피보나치 수 - 6에서 [백준 11444번] 피보나치 수 6 (Python3) (tistory.com) 당시에는 행렬 제곱으로 풀지는 않았지만 피보나치 수를 행렬로 바꿔서 푸는 방법을 배웠었는데, 이를 이용하면 아주 쉽게 풀 수 있다.

 

피보나치 수에서 점화식을 이용한 행렬이 [[1,1],[1,0]] 이었던 것처럼 이번 문제의 행렬은 [[4,-1],[1,0]]이 된다. 그리고 분할정복을 이용한 거듭제곱을 이용해서 풀면 된다.

 

그런데 문제는 저 점화식이 왜 성립하는지는 알 수가 없다는 것이다. 숫자를 나열하면 1초만에 보이지만 증명해보라고 하면 흠; 어려운 문제이다.

 

 

오늘의 교훈) 왜 저런 점화식이 성립하는지 고민해보자