Algorithm/Divide and Conquer1 BOJ G4 10830 행렬제곱 JAVA 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 문제 읽기 어제 풀었던 문제와 비슷한 부분이 있어서 분할 정복을 빠르게 떠올렸다. 행렬 곱 식을 통해 문제를 풀었다. 문제 풀기 문제를 요약하면 행렬의 거듭 제곱 문제이다. 행렬 내가 행렬 곱을 제대로 알고 있는지 몰라서 일단 연습해봤는데 맞는 것 같다. 이렇게 계산할 수 있고, 다음과 같은 식을 얻을 수 있다. 분할 정복을 이용한 거듭 제곱 → O(logN) 두 번째로 고려할 것은 B의 크기이다. N도 최대 5로 작고, 행렬의 원소도 1000 이하이므로 작은데, B의 크기가 .. 2024. 1. 16. 이전 1 다음
