기록

문제 https://www.acmicpc.net/problem/10830 10830번: 행렬 제곱 크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 1) 분할 정복을 이용한 거듭제곱 number을 n번 곱한다고 하면, 아래처럼 적을 수 있다. 이를 행렬에도 적용하면, 문제를 해결할 수 있다. def power(number, n) : if n==0 : return 1 elif n이 짝수 : return power(number², n//2) elif n이 홀수 : return number*power(number², n//2) 문제에서는 n의 최대값을..

문제 1629번: 곱셈 첫째 줄에 A, B, C가 빈 칸을 사이에 두고 순서대로 주어진다. A, B, C는 모두 2,147,483,647 이하의 자연수이다. www.acmicpc.net 풀이 A, B가 커짐에 따라 A**B의 수행시간이 늘어난다. 따라서 이문제는 분할 정복을 이용하여 해결해야 한다. 모듈러 연산의 성질과 분할정복을 이용하면 B번의 연산을 log2B번으로 줄일 수 있다. 코드 def f(A, B) : if B==0 : return 1 if B%2==0 : tmp1 = f(A, int(B / 2)) ans = (tmp1 * tmp1) % C else : tmp1 = f(A, int(B / 2)) tmp2 = (tmp1 * (A % C)) % C ans = (tmp1 * tmp2) % C re..