알고리즘 |
분할 정복, 분할 정복을 이용한 거듭제곱 |
[문제 본문]
더보기
문제
크기가 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제곱한 결과를 출력한다.
예제 입력 1
2 5 1 2 3 4
예제 출력 1
69 558 337 406
예제 입력 2
3 3 1 2 3 4 5 6 7 8 9
예제 출력 2
468 576 684 62 305 548 656 34 412
예제 입력 3
5 10 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1 1 0 0 0 1
예제 출력 3
512 0 0 0 512 512 0 0 0 512 512 0 0 0 512 512 0 0 0 512 512 0 0 0 512
[푼 코드]
#include <iostream>
long long matrix[6][6];
long long currentMatrix[6][6];
long long N, B;
using namespace std;
void CalMatrix(long long m1[6][6], long long m2[6][6])
{
long long tempArr[6][6];
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
tempArr[i][j] = 0;
for (int k = 0; k < N; k++)
{
tempArr[i][j] += (m1[i][k]) * (m2[k][j]);
}
tempArr[i][j] %= 1000;
}
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
m1[i][j] = tempArr[i][j];
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie();
cout.tie();
cin >> N >> B;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cin >> matrix[i][j];
}
currentMatrix[i][i] = 1;
}
while(B)
{
if (B % 2 == 1)
{
CalMatrix(currentMatrix, matrix);
}
CalMatrix(matrix, matrix);
B /= 2;
}
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
cout << currentMatrix[i][j] << ' ';
}
cout << "\n";
}
return 0;
}
#분할정복알고리즘 #행렬곱셈알고리즘 #수학알고리즘 #분할정복거듭제곱
728x90
반응형
'알고리즘 > solved.ac' 카테고리의 다른 글
[class4] (백준 17144) 미세먼지 안녕! (0) | 2022.03.09 |
---|---|
[class4] (백준 14938) 서강그라운드 (0) | 2022.03.09 |
[class4] (백준 9935) 문자열 폭발 (0) | 2022.03.07 |
[class4] (백준 2448) 별 찍기 - 11 (0) | 2022.03.06 |
[class4] (백준 2096) 내려가기 (0) | 2022.03.04 |