백준 10830 행렬제곱
https://www.acmicpc.net/problem/10830
행렬제곱문제
분할정복의 기초를 다지기에 진짜좋은문제인거같다..ㅎㅎ;;
다른 골드5 문제들은 분할정복 도되지만 다른 풀이가더 매끄러운? 문제들이많아서
해당문제를 풀었다.
골드3 골드2까지 풀고 얼른 넘어가도록 하자
메인로직
- 2로 나눳을때 나머지가 1인지 0인지 체크
ex. 5=> 2 2+ 1 // 4 => 2 2 - 1번의 로직을 1이 될떄까지 재귀를 타줌 => 1이 될떄는 원래 행렬반환
- 그럼 사실상 2 또는 3이 될떄가지 재귀가 되는데 그때부터 행렬연산을 통해 return 해줌
- 연산할때 %1000 해주고 출력할때 %1000 해주기
import java.io.*;
import java.util.*;
public class 행렬제곱 {
static int[][] array;
static int N;
static long B;
public static void main(String[] args) throws Exception{
// TODO Auto-generated method stub
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
B = Long.parseLong(st.nextToken());
array = new int[N][N];
for(int i=0;i<N;i++) {
st = new StringTokenizer(br.readLine());
for(int j=0;j<N;j++) {
array[i][j] = Integer.parseInt(st.nextToken())%1000;
}
}
int[][] answer = div(B);
StringBuilder sb = new StringBuilder();
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
sb.append(answer[i][j]%1000).append(" ");
}
sb.append("\n");
}
System.out.println(sb);
}
public static int[][] div(long count){
if(count==1) {
return array;
}
int[][] canswer = new int[N][N];
int[][] fanswer = div(count/2);
if(count%2==1) {
canswer = cal(fanswer,fanswer);
canswer = cal(canswer,array);
}
else {
canswer = cal(fanswer,fanswer);
}
return canswer;
}
public static int[][] cal(int[][] a,int[][]b){
int[][] canswer = new int[N][N];
/*
1 2 1 2 (0,0)1*1(0,0) +(0,1)2*3(1,0)
3 4 3 4
*/
for(int i=0;i<N;i++) {
for(int j=0;j<N;j++) {
int sum = 0;
for(int k=0;k<N;k++) {
sum += a[i][k]*b[k][j];
}
canswer[i][j] = sum%1000;
}
}
return canswer;
}
}
long 처리와.. ㅎㅎ;; 재귀를 잘못설정 .. 그리고 많은 배열선언으로 인해 시행착오가있었다 ㅎㅎ;;
얼른 2 3으로넘어가자
Author And Source
이 문제에 관하여(백준 10830 행렬제곱), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@tekies09/백준-10830-행렬제곱저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)