분할 정복 > 1629번, 10830번

1629번

 

long 타입을 사용해도 정수의 오버플로우가 발생하므로 모듈러 합동 공식을 사용해야 한다

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

public class baekjoon1629 {
    static int A;
    static int B;
    static int C;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        A = Integer.parseInt(st.nextToken());
        B = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        System.out.println(multiple(A, B));
    }

    // ex) 3^4 = (3*3) * (3*3)
    public static long multiple(long x, long n) {
        if (n == 1) {
            return x % C;
        }

        long tmp = multiple(x, n / 2);

        // 모듈러 합동 공식: (a * b) % C = ((a % C)*(b % C)) % C
        // tmp * tmp * A % C = ((tmp * tmp % C) * A) % C
        if (n % 2 == 1) {
            return ((tmp * tmp % C) * A) % C;
        }
        return tmp * tmp % C;
    }
}

 

10830번

 

행렬의 거듭 제곱을 이용한 문제이다

 

 

지수를 절반으로 나눠 재귀를 호출한다

지수가 홀수인 경우 행렬A ^5 = 행렬A^2 * 행렬A^2 * 행렬A

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

public class baekjoon10830 {
    static int N;
    static long B;
    static int [][] grid;
    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());
        grid = new int[N][N];
        String [] str;
        for(int i = 0; i<N; i++) {
            str = br.readLine().split(" ");
            for(int j = 0; j<N; j++) {
                // 초기 행렬에도 1000으로 나눈 나머지 값으로 초기화 
                // > B = 1인 경우 행렬의 숫자가 1000이 넘을 경우 나머지가 아닌 기존 값이 그대로 출력되므로
                grid[i][j] = Integer.parseInt(str[j]) % 1000;
            }
        }
        int [][] output = partition(grid, B);
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i<N; i++) {
            for(int j = 0; j<N; j++) {
                sb.append(output[i][j]+" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
    public static int[][] partition (int [][] procession, long num) {
        if(num == 1L) {
            return procession;
        }
        int [][] tmp = partition(grid, num/2);

        tmp = calculator(tmp, tmp);

        if(num % 2 == 1L) {
            tmp = calculator(tmp, grid);
        }

        return tmp;
    }
    public static int[][] calculator (int [][] grid1, int [][] grid2) {
        int [][] tmp = new int[N][N];
        for(int i = 0; i<N; i++) {
            for(int j = 0; j<N; j++) {
                for(int k = 0; k<N; k++) {
                    tmp[i][j] += grid1[i][k] * grid2[k][j];
                    tmp[i][j] %= 1000;
                }
            }
        }
        return tmp;
    }
}