백준 10830번 문제(행렬 제곱) 파이썬(Python) 풀이 [로밍맨]

문제 링크

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

 

정답 코드는 아래와 같습니다.

DIV = 1000
 
def mul(A, B, n):
  rst = [[0] * n for _ in range(n)]
  for i in range(n):
    for j in range(n):
      for k in range(n):
        rst[i][j] += (A[i][k] * B[k][j])
      rst[i][j] %= DIV
  return rst
 
def solve():
  n, b = [int(x) for x in input().split()]
  mat = []
  for _ in range(n):
    tmp = [int(x) for x in input().split()]
    mat.append(tmp)
  for i in range(n):
    for j in range(n):
      mat[i][j] %= DIV
  rst = [[0] * n for _ in range(n)]
  for i in range(n):
    rst[i][i] = 1
  while b != 0:
    if b % 2 == 1:
      rst = mul(rst, mat, n)
    mat = mul(mat, mat, n)
    b >>= 1
  for i in range(n):
    for j in range(n-1):
      print(rst[i][j], end=' ')
    print(rst[i][-1])
 
solve()
 

 

수학 성질 몇 가지를 알아야 풀 수 있는 문제입니다.

일단 행렬 곱셈과 그 성질(결합법칙이 성립) 그리고 행렬의 곱셈에 대한 항등원(E)에 대하여 알아야 합니다.

너무 수학적인 내용이라 제가 여기서 정리하지는 않겠습니다만,

행렬은 다양한 알고리즘과 AI에서 사용되므로 행렬에 대한 내용은 익혀두시길 권장합니다.

 

그 다음으로 알아야 하는 것은,

모든 미지수가 정수라고 가정하고, P와 Q가 있을 때,

각각을 x로 나눈 몫과 나머지를 각각 a, b 그리고 c, d 라고 할 때, 즉,

P = ax + b

Q = cx + d

일 때,

P와 Q를 곱한 수를 x로 나눈 나머지는 P와 Q각각을 x로 나눈 나머지 b와 d를 곱한 수의 나머지와 동일하다는 것입니다.

즉,

PQ = (ax + b)(cx + d)

     = acx^2 + adx + bcx + bd

     = (acx + ad + bc)x + bd

여기서 (acx + ad + bc)x 는 x 로 나누어 떨어지기 때문에 결국

PQ의 나머지와 bd 의 나머지가 같다는 것을 알 수 있습니다.

실전에서도 은근히 많이 사용되는 성질이므로 꼭 이해하고 익혀두시길 권장합니다.

 

728x90

 

본격적으로 풀이를 하기에 앞서서, 혹시 채팅창 도배 같은 거 해본 경험 있으신가요?

예를 들어서 "ㅋㅋㅋㅋㅋㅋㅋㅋㅋ <중략>  ㅋㅋㅋㅋㅋㅋㅋㅋㅋ" 라고 도배를 하고 싶으면 어떻게 하나요?

PC에서는 키보드의 'ㅋ' 를 누른 상태로 있다가 한참 많아졌다고 생각하면 엔터를 치겠죠.

스마트폰에서는 그런데 조금 힘듭니다. 'ㅋ' 를 계속 터치해야 합니다.

몇 번 하다보면 이렇게 해서는 도배를 하기 어렵겠다는 판단이 들고, 적당히 몇 번 'ㅋ'를 친 다음에 복사합니다.

그리고 뒤에 붙여 넣으면 2배가 됩니다. 그 다음에 다시 전체를 복사하고 또 뒤에 붙여넣습니다. 다시 2배가 됩니다.

이렇게 하면 빠르게 도배를 하기 위한 문자열을 완성할 수 있습니다. 이런식으로 된다는 겁니다.

 

맨 처음 몇 번 정도는 직접 치고,

ㅋㅋㅋㅋ

복사해서 뒤에 붙임

ㅋㅋㅋㅋㅋㅋㅋㅋ

이걸 또 복사해서 뒤에 붙임

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이걸 또 복사해서 뒤에 붙임

ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

이런식으로 빠르게 긴 문자열을 만들 수 있습니다.

 

이 문제는 도배할 때 긴 문자열을 만드는 것과 비슷한 원리로 풀립니다.

A^16 을 구한다고 할 때, A를 15번 곱해서 구하는 것이 아니라,

A^2 를 구하고 이를 제곱하여 A^4 를 구하고, 이를 제곱하여 A^8 을 구하고 이를 제곱하여 A^16을 구하는 것입니다.

즉, 4번이면 A^16 을 구할 수 있는 것이지요.

그럼 A^20은 어떻게 구할 수 있을까요?

결국 A의 제곱수의 곱으로 표현하여서 상호간에 곱셈을 진행하도록 하는 것입니다.

즉, A^20 = A^16 * A^4 이므로, A^16 을 구하는 과정에서 A^4 를 구했을 것이고 이를 서로 곱하여 정답을 얻을 수 있습니다.

하나만 더 예를 들어서 A^23이라면,

23 = 16 + 4 + 2 + 1 이므로 아래와 같이 계산할 수 있습니다.

A^23 = A^16 * A^4 * A^2 * A

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=35r_4cw9its 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)