10830번 - 행렬 제곱

2024-07-03

#JAVA#백준

문제 링크

문제 풀이 시간 : 1시간

문제 요약

•
크기가 N * N인 행렬 A가 있다.

•
A의 B제곱을 구하라.

•
각 원소를 1,000 으로 나눈 나머지를 출력한다.

•
2 ≤ N ≤ 5

•
1 ≤ B ≤ 100,000,000,000

문제 풀이

옛날에 풀려고 문제를 읽었다가 B의 범위를 보고 바로 도망쳤던 문제이다.

뭐 풀지 찾아보다가 뭔가 풀 수 있을 것 같아서 이번에 풀게 되었다.

행렬의 제곱을 할 때, 1제곱 * 1제곱을 하면 2제곱,

2제곱 * 2제곱를 하면 4제곱이 나온다.

이걸 이용해서 분할정복법을 사용하면 B도 많이 작아지게되지 않을까?

라는 생각으로 코드를 짰다.

초기 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N;
    public static long B;
    public static int[][] base;

    public static int[][] find(long num){ //행렬 찾기
        if(num == 1){
            return base;
        }
        return calc(find(num/2),find(num-num/2));
    }

    public static int[][] calc(int[][] arr1, int[][] arr2){ //행렬 곱셉 함수
        int[][] result = new int[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int temp = 0;
                for(int k=0;k<N;k++){
                    temp += arr1[i][k]*arr2[k][j];
                }
                result[i][j] = temp%1000;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());

        base = new int[N][N];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                base[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] result = find(B);
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                System.out.printf(result[i][j]+" ");
            }
            System.out.println();
        }
    }
}

얼레?

이랬더니 Number Format 에러가 떴다.

생전 보지도 못했던 에러였는데

알고보니 문자열에서 숫자로 변환될 때 발생한다고 한다.

근데 아무리 봐도 내 코드에서 숫자로 변환하는거에는 문제가 없는데?

백준 오랜만에 풀었더니 고장났나? 라는 생각을 했다.

근데 알고보니 B의 범위가 1000억이라는 것을 간과했다.

그래서 B를 Long으로 변경해주었다.

수정 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N;
    public static long B;
    public static int[][] base;

    public static int[][] find(long num){
        if(num == 1){
            return base;
        }
        return calc(find(num/2),find(num-num/2));
    }

    public static int[][] calc(int[][] arr1, int[][] arr2){
        int[][] result = new int[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int temp = 0;
                for(int k=0;k<N;k++){
                    temp += arr1[i][k]*arr2[k][j];
                }
                result[i][j] = temp%1000;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        B = Long.parseLong(st.nextToken());

        base = new int[N][N];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                base[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] result = find(B);
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                System.out.printf(result[i][j]+" ");
            }
            System.out.println();
        }
    }
}

얼레?

이번엔 시간초과가 났다.

어느정도 예상은 했는데 제출과 동시에 시간초과가 나서 살짝 당황했다.

이거는 알고리즘 수업시간에도 배웠듯이 분할정복법의 단점인 같은 계산을 반복하는 것에서 생긴 것이다.

Java

public static int[][] find(long num){
        if(num == 1){
            return base;
        }
        return calc(find(num/2),find(num-num/2));
    }

위의 코드에서 find()함수가 불필요하게 많이 호출되는 것이다.

이걸 해결하기 위해 미리 find(num/2)를 계산해두어 여러번 계산하지 않도록 만들어 준다.

수정 코드2

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N;
    public static long B;
    public static int[][] base;

    public static int[][] find(long num){
        if(num == 1){
            return base;
        }
        int[][] save = find(num/2); //미리 계산해서 저장

        if(num%2==1){ //현재가 홀수번째라면
            return calc(calc(save,save),base);
        }
        else{
            return calc(save,save);
        }
    }

    public static int[][] calc(int[][] arr1, int[][] arr2){
        int[][] result = new int[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int temp = 0;
                for(int k=0;k<N;k++){
                    temp += arr1[i][k]*arr2[k][j];
                }
                result[i][j] = temp%1000;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        B = Long.parseLong(st.nextToken());

        base = new int[N][N];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                base[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        int[][] result = find(B);
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                System.out.printf(result[i][j]+" ");
            }
            System.out.println();
        }
    }
}

얼레?

이번엔 채점이 잘 되다가 80%에서 틀렸다고 뜬다..

무엇이 문제일까??

만약 입력이 아래와 같이 주어진다고 생각하자.

Java

2 1
1000 1000
1000 1000

그럼 위의 코드에서는 아래와 같은 출력이 나온다.

Java

1000 1000
1000 1000

그렇지만 정답은 1000으로 나누어줘야 하기 때문에

Java

0 0
0 0

위와 같이 나와야 한다.

그래서 초기 행렬을 입력받는 과정에서 1000을 나눠주어 해당 문제를 해결할 수 있었다.

정답 코드

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static int N;
    public static long B;
    public static int[][] base;

    public static int[][] find(long num){
        if(num == 1){
            return base;
        }
        int[][] save = find(num/2);

        if(num%2==1){
            return calc(calc(save,save),base);
        }
        else{
            return calc(save,save);
        }
    }

    public static int[][] calc(int[][] arr1, int[][] arr2){
        int[][] result = new int[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                int temp = 0;
                for(int k=0;k<N;k++){
                    temp += arr1[i][k]*arr2[k][j];
                }
                result[i][j] = temp%1000;
            }
        }
        return result;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        B = Long.parseLong(st.nextToken());

        base = new int[N][N];
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0;j<N;j++){
                base[i][j] = Integer.parseInt(st.nextToken())%1000; //입력에서 1000 나눠주기
            }
        }
        int[][] result = find(B);
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                System.out.printf(result[i][j]+" ");
            }
            System.out.println();
        }
    }
}