[백준]10830 - 행렬 제곱

고려사항

• 행렬A로 들어오는 각 원소의 값이 1000보다 작거나 ‘같은’자연수라고 했는데 ‘같은’ 조건을 무시해서 b==1인 경우 어차피 100보다 다 작을테니 그대로 반환해야지~ 했다가 틀림.
• b==1인 경우에도 원소로 1000이 들어올 것을 대비하여 1000으로 나누어 반환하는 코드 추가
• 행렬 곱셈, 분할 정복(Divide and Conquer), 모듈러 연산

코드

1차 시도

def mul(X,Y,n):
  res=[[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j]+=X[i][k] * Y[k][j]
      res[i][j]%=1000
  return res

def dc(a,b,n):
  if b==1:
    return a
  tmp=dc(a,b//2,n)
  if b%2:
    return mul(mul(tmp,tmp,n),a,n)
  else:
    return mul(tmp,tmp,n)
       
n,b=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
  
res=dc(a,b,n)

for i in res:
  print(" ".join(map(str,i)))

최종

#G4_10830_행렬 제곱

def mul(X,Y,n):
  res=[[0]*n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        res[i][j]+=X[i][k] * Y[k][j]
      res[i][j]%=1000
  return res

def dc(a,b,n):
  if b==1:
    return [[a[i][j]%1000 for j in range(n)] for i in range(n)] # 이 부분 수정
  tmp=dc(a,b//2,n)
  if b%2:
    return mul(mul(tmp,tmp,n),a,n)
  else:
    return mul(tmp,tmp,n)
       
n,b=map(int,input().split())
a=[]
for i in range(n):
  a.append(list(map(int,input().split())))
  
res=dc(a,b,n)

for i in res:
  print(" ".join(map(str,i)))