[BOJ] 10830 행렬 제곱 (C/C++)

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이다.

출력

첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.

---

어제 풀어봤던 문제보다 먼저 풀었어야 했을 것 같은 문제다. 순서는 거꾸로지만 그래도 이제는 분할 정복을 이용한 행렬 곱셈에 대해 알게 되었다. 

 

이 문제는 단순히 행렬 제곱을 구하는 문제지만 N이 상당히 파멸적인 숫자까지 들어올 수 있다. 따라서 그냥 무식하게 곱해도 답은 나오겠지만 시간 제약이 있다면 말이 달라진다. 그래서 사용한 방법이 분할 정복이다. 계산식을 나누다 보면 중복되는 계산이 있다는 것을 발견할 수 있다. 그래서 분할 정복 기법을 적용할 수 있는데, A를 5번 곱하는 과정을 예시로 들면 다음과 같다. (1은 단위행렬)

반복 횟수	A	B	ans
1	A	10	1
2	A^2	5	1
3	A^4	2	A^2
4	A^8	1	A^2
5	A^16	0	A^10

마지막의 ans 변수에 A^10의 값이 들어가있는 것을 볼 수 있다. 실제로 과정을 써보니 직관적으로 이해했던 과정이랑 미묘하게 달랐다. 직접 써보길 잘한 것 같다.

 

그리고 어제도 그렇고 행렬 곱셈을 만들기 위해서 연산자 오버 로딩을 사용했다. 사실 이걸 많이 안 써봐서 익숙하지 않다. 가끔 문제를 풀다 보면 연산자 오버 로딩을 사용하고 싶을 때가 있는데, 그때마다 다른 방법으로 돌아가곤 했다. 잘 다룰 수만 있다면 여기저기에 써먹기 좋을 것 같다. 

 

 

후기)

이런 문제를 한문제만 더 풀어봐야겠다.