[백준] 10830.행렬 제곱 (Swift, Java)

[백준] 10830.행렬 제곱 (Swift, Java)

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

10830번: 행렬 제곱

문제

크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.

첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)

둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.

이해

1. 단순 제곱

문제를 처음 읽었을 때 당연히 처음 떠오르는 해답은 단순 제곱이었습니다. 행렬을 B 번 만큼 곱해주면 되는거 아냐? 라는 생각이 들면서도 역시 문제가 그렇게 단순할 리 없다는 생각과, O(B^2) 만큼의 시간이 걸릴것이라고 예상했기 때문에 해당 방법은 과감하게 버렸습니다.

2. 이진탐색 - O(logN)

가장 힌트가 되었던건 시간복잡도였습니다. 어떤 식으로 문제를 풀어야 할지 몰라 검색 도중, O(logN) 이라는 키워드가 가장 큰 아이디어가 되었습니다.

 

이진탐색은 데이터를 반씩 나누어가며 탐색하는 방법으로 이진트리의 모양을 하고있어 시간복잡도가 O(logN) 이지만, 저는 이진탐색의 역순(?)과 비슷한 방향으로 문제를 풀어나갔습니다.

---

먼저 제곱을 해야하는 횟수를 N 이라고 하고, N 은 11 이 주어졌다고 가정하겠습니다.

그림에서 각 원은 행렬을 뜻합니다.

---

그 다음 행렬을 2개씩 짝지어 곱셈을 진행합니다. 이때 N 이 홀수라면 무조건 하나의 행렬이 남게 되는데, 이는 odd 라는 이름의 변수에 저장해둡니다.

 

행렬을 2개씩 짝지어 곱셈을 진행했기 때문에 남은 연산 수는 1/2 이 됩니다. 그렇기 때문에 N/2 인 5 를 다시 N 에 저장해줍니다.

---

다시 행렬을 두개씩 짝지어 곱해주고 N/=2 를 진행합니다. 5 또한 홀수이기 때문에 하나의 행렬이 남게 되는데 이는 이전에 존재하던 odd 와 곱해준 후 그 결과값을 다시 odd 에 저장해줍니다.

 

odd 를 계속해서 업데이트 시켜주는 이유는 짝지어 계산한 마지막 결과에 곱해주기 위함입니다.

이후 남은 2개의 행렬을 곱해주고 N/=2 를 진행합니다. N이 1이 되었기 때문에 더 이상 짝지어 곱해줄 행렬을 존재하지 않습니다.

---

하지만 아직 곱해주지 않은 나머지 행렬 odd 가 남았기 때문에 이 둘을 곱해주면 정답이 도출되게 됩니다.

위 그림은 이진트리의 모양을 하고있기 때문에 O(logN) 의 시간복잡도를 가지게 됩니다.

---

전체 코드

Swift

Java