https://www.acmicpc.net/problem/10830
10830번: 행렬 제곱
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
www.acmicpc.net
수학 + 분할정복 문제다.
풀이
행렬의 제곱연산을 수행하는 함수를 생성. B번의 곱셈을 수행하면 간단하겠지만, B의 최댓값이 크기 때문에 거듭제곱의 원리를 응용하여 연산 횟수를 줄여야 한다.
마지막에 출력해 줄 result 배열을 단위행렬로 초기화한 뒤, B가 0이 될 때까지 반복문을 순환한다. 매 반복문마다 A행렬은 거듭제곱연산이 이루어지고, B가 홀수일 경우에는 result배열에 A행렬을 곱해주는 연산을 수행하면 올바른 결과를 출력할 수 있다.
A의 7 제곱 행렬을 구한다고 가정했을 경우 아래와 같은 형태로 연산이 수행된다.
| B | Result | Matrix |
| 7 | A¹ | A² = (A¹ * A¹) |
| 3 | A¹ * A² | A⁴ = (A² * A²) |
| 1 | A¹ * A² * A⁴ | A⁸ = (A⁴ * A⁴) |
| 0 | 결과 출력 |
정답 코드
'Problem Solving > BOJ' 카테고리의 다른 글
| [2533] 사회망 서비스(SNS) (0) | 2023.02.13 |
|---|---|
| [11054] 가장 긴 바이토닉 부분 수열 (0) | 2023.02.12 |
| [2638] 치즈 (0) | 2023.02.10 |
| [11779] 최소비용 구하기 2 (0) | 2023.02.10 |
| [11444] 피보나치 수 6 (0) | 2023.02.08 |