[백준 17272번] 리그 오브 레전설 (Large)

def multiply(A,B):
  S = [[0]*M for i in range(M)]
  for i in range(M):
    for j in range(M):
      for k in range(M):
        S[i][j] += A[i][k]*B[k][j]
      S[i][j] %= 10**9+7
  return S

def cal(A,n):
  if n==0:
    return [[int(i==j) for j in range(M)] for i in range(M)]
  if n==1:
    return A
  c = cal(A,n//2); c2 = multiply(c,c)
  return multiply(c2,A) if n%2 else c2  

N,M = map(int,input().split())
print(cal([[int(i==j==0 or i==M-1 and j==0 or j-i==1) for j in range(M)] for i in range(M)],N)[0][0])

간단한 인접행렬 경우의 수 문제

길의 개수 [백준 1533번] 길의 개수 (Python3) (tistory.com) 하위호환격 문제이다.

 

길의 개수 문제를 풀었을 때, x에서 y까지 걸리는 시간이 n초인 경우 행을 n개로 쪼갰던 것처럼, 이 문제는 1에서 1까지 가는 경로가 M초가 걸리는 길이 있다고 생각하고, 행을 M개로 쪼갠 뒤 M초 후에 1에 도착하도록 행렬을 짜면 된다.

그리고 위에서 짠 행렬을 분할정복을 통한 거듭제곱으로 N번 제곱해주면 된다.

 

 

오늘의 교훈) 인접행렬은 유용하다.