문제
크기가 N*N인 행렬 A가 주어진다. 이때, A의 B제곱을 구하는 프로그램을 작성하시오. 수가 매우 커질 수 있으니, A^B의 각 원소를 1,000으로 나눈 나머지를 출력한다.
입력
첫째 줄에 행렬의 크기 N과 B가 주어진다. (2 ≤ N ≤ 5, 1 ≤ B ≤ 100,000,000,000)
둘째 줄부터 N개의 줄에 행렬의 각 원소가 주어진다. 행렬의 각 원소는 1,000보다 작거나 같은 자연수 또는 0이다.
출력
첫째 줄부터 N개의 줄에 걸쳐 행렬 A를 B제곱한 결과를 출력한다.
풀이
애초에 B
의 범위가 int
형을 넘어갈 정도로 크기 때문에 당연히 단순한 방법으로는 시간 초과
가 나온다. 따라서 A^B
의 계산 속도를 비약적으로 높힐 방법을 떠올려야 하는데 여기서 분할정복
을 적용할 수 있다. 아이디어는 다음과 같다.
- B가 홀수일 경우: A * A^(B-1)
- B가 짝수일 경우: A^(B/2) * A^(B/2)
- B가 1일 경우(기저 사례): A 를 그대로 반환
위와 같은 알고리즘을 사용하면 O(logN) 의 시간복잡도로 계산을 완료할 수 있다.
그런데 이 때 중복 계산
이 재귀가 깊어질수록 기하급수적으로 발생하기 때문에 메모이제이션
기법을 이용해 이를 방지해야한다. 행렬을 표현하기 위해 원소로 2차원 배열
을 사용하기 때문에 map
을 이용해 메모이제이션
을 구현해주어야 한다.
전체 코드
1 |
|
- Post link: https://blog.yjyoon.dev/boj/2020/12/23/boj-10830/
- Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 3.0 unless stating additionally.