목록10830 (1)

코딩성장스토리

10830번 : 행렬 제곱

https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 이 문제는 100,000,000,000번 곱해야하는 문제이다 . 즉 시간복잡도가 O(log n)이 아니면 불가능 하다. 그래서 분할 정복을 생각하였다. 문제 풀이는 제곱수가 n이라 하고 행렬 a가 있다고 할 때, ex)n=10이라고 하자. 나는 재귀로 풀었기에 n은 1,2,4,5,10으로 올라가는 형태이다. 즉 n=1일때 A n=2일때 A*A=A^2 n=4일 떄 는 (A^2)*(A^2)=A^4 n=5일 때 는 ..
백준 코딩 2022. 7. 24. 13:49
이전 Prev 1 Next 다음