[백준 10830 C++] 행렬 제곱

오늘은 백준 10830 퍼즐에 대해 다뤄볼 예정이다.

백준 10830번 문제는 행렬의 제곱 값을 구하는 문제이다.

10830번: 행렬 제곱

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

www.acmicpc.net

문제 설명

입력 받은 행렬의 거듭 제곱 값을 구해야하는 문제이다.

예를 들어, 아래와 같은 행렬이 존재한다고 가정해보자.

그럼, 위 행렬의 제곱 값을 구해보면, 아래와 같은 과정을 거치게 된다.

1 2 3 1 2 3 (1 X 1 + 2 X 4 + 3 X 7), (1 X 2 + 2 X 5 + 3 X 8), (1 X 3 + 2 X 6 + 3 X 9)

4 5 6 X 4 5 6 = (4 X 1 + 5 X 4 + 6 X 7), (4 X 2 + 5 X 5 + 6 X 8), (4 X 3 + 5 X 6 + 6 X 9)

7 8 9 7 8 9 (7 X 1 + 8 X 4 + 9 X 7), (7 X 2 + 8 X 5 + 9 X 8), (7 X 3 + 8 X 6 + 9 X 9)

결론적으로, 아래와 같은 결과가 나옴을 알 수 있다.

그럼 본론으로 들어가보자.

문제 풀이

우선 위 문제를 풀기 위해서는 시간 초과를 해결해야한다. 같은 반복되는 연산을 최소화하기 위해 어떤 방식을 써야할까?

이 문제의 핵심은 행렬의 곱을 진행할 때 거듭 제곱 값이 동일한 행렬 끼리 연산 하는 것이다.

다시 말해, 특정 행렬의 여덟 제곱한 값을 얻기 위해서는 (행렬의 네 제곱 X 행렬의 네 제곱) 이와 같은 방식으로 계산하는 것이다.

그럼, 행렬의 네 제곱은 (행렬의 제곱 X 행렬의 제곱) 연산을 통해 값을 얻을 수 있을 것이다.

위 문제를 풀기 위해, 총 3 가지 행렬을 저장하기 위한 배열(입력 받은 행렬, 계산된 행렬, 현재 행렬)이 필요하다.

이를 코드로 나타내면, 아래와 같이 구현할 수 있다.

STEADINESS