목록행렬 제곱 (1)

Don't give up!

[백준] 10830번 : 행렬 제곱 (java)

10830번: 행렬 제곱 (acmicpc.net) 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 어떻게 생각하고 문제를 풀었는가? NxN 행렬 A의 B제곱은 x1+x2+....=B를 만족하는 A의 xi제곱들을 곱하여 나타낼 수 있습니다. 이때 xi의 값들이 2의 제곱으로 나타내어질 수 있도록 한다면 A의 제곱, 4제곱, 8제곱을 구하여 결과를 빠르게 구할 수 있습니다. 이러한 xi 값들은 B를 2진수로 표현하여 1을 갖는 자리를 확인함으로써 빠르게 찾아낼 수 있을 것이라고 생각하였습니다. 코드 import java.io.*..
Coding Test/BOJ 2021. 8. 18. 16:34
이전 Prev 1 Next 다음