백준 10830 행렬 제곱 [java, c++]

24 Jun 2022 in Develop / Solving

java

c++로 풀려고 했는데, 2차원 배열을 함수에 전달하고 리턴받는 과정이 좀 복잡해서, 일단 자바로 풀고 다른 사람들의 코드를 훔쳐보며 c++로 한번 더 풀기로 했다.

문제 분석

• N*N의 행렬 A가 주어진다. A의 B제곱을 구하는데, 각 원소를 1000으로 나눈 나머지를 출력하여라.

입력조건

행렬의 크기 A 제곱할 횟수 B

풀이과정

• 아주 대표적인 분할정복 문제.
• 제곱할 횟수를 2로 계속 나누어 가면 서
• 계산 횟수를 반으로 줄여 연산 진행.

전체 코드

• java

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

public class BJ10830_행렬제곱 {
    static int psize;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        long num;

        psize = Integer.parseInt(st.nextToken());
        num = Long.parseLong(st.nextToken());

        int[][] p = new int[psize][psize];
        
        for(int i = 0; i < psize; i++){
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < psize; j++) 
                p[i][j] = Integer.parseInt(st.nextToken()) % 1000;
        }
        // 입력 완료.

        int[][] ans = calc(num, p);

        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < psize; i++){
            for(int j = 0; j < psize; j++)
                sb.append(ans[i][j] + " ");
            sb.append("\n");
        }
        System.out.println(sb);
    }

    public static int[][] calc(long num, int[][] p) {
        if(num == 1) return p;

        int[][] x = calc(num/2, p);
        int[][] mx = multiple(x, x);
        
        // System.out.println(num);
        // for(int i = 0; i < psize; i++){
        //     for(int j = 0; j < psize; j++){
        //         System.out.print(mx[i][j] + " ");
        //     }
        //     System.out.println();
        // }

        if(num % 2 == 0) return mx;
        else             return multiple(mx, p);
    }

    public static  int[][] multiple(int[][] p1, int[][] p2) {
        int[][] newp = new int[psize][psize];

        for(int i = 0; i < psize; i++) {
            for(int j = 0; j < psize; j++) {
                int tmp = 0;
                
                for(int t = 0; t < psize; t++)
                    tmp += p1[i][t] * p2[t][j];

                newp[i][j] = tmp % 1000;
            }
        }
        return newp;
    }
}

C++ 추가 풀이

• c++은 2차원 배열을 임의의 사이즈로 함수에 전달하고 리턴받는 것이 매우 불편하다.
  다른 사람들은 어떤지 잘 모르겠고 나느 불편하다. 매우 불편하다. java하게 해줘

• 다른 사람들의 풀이를 뒤져본 결과, struct를 이용해서 배열을 넣어놓은 뒤, 이 struct를 반환하거나, 그냥 전역으로 배열을 선언해서 여기저기서 사용하는 걸로 보인다.

• 나는 이중포인터 형태의 자료를 반환하는 함수를 만들어서, 이를 통해 처리하였다.
• 다 쓰고 생각했는데, 이 방법은 c++에서 쓸 수 있는 가장 java같은 방법이라고 생각한다.
• 포인터 어려워 ㅠㅠ

전체 코드

#include <iostream>

using namespace std;

static int psize;

int** calc(int** p1, int** p2){
    int** newp = new int*[psize];
    for(int i = 0; i < psize; i++) newp[i] = new int[psize];

    for(int i = 0; i < psize; i++) {
        for(int j = 0; j < psize; j++) {
            int tmp = 0;
            
            for(int t = 0; t < psize; t++)
                tmp += p1[i][t] * p2[t][j];

            newp[i][j] = tmp % 1000;
        }
    }
    return newp;
}

int** multiple(long long n, int** p){
    if(n == 1) return p;

    int** x = multiple(n/2, p);
    int** mx = calc(x, x);

    if(n % 2 == 0) return mx;
    else           return calc(mx, p);
}

int main() {
    long long num;
    cin >> psize >> num;

    // 배열 생성 및 초기화
    int** p = new int*[psize];
    for(int i = 0; i < psize; i++) {
        p[i] = new int[psize];
        
        for(int j = 0; j < psize; j++) {
            int tmp;
            cin >> tmp;
            p[i][j] = tmp % 1000;
        }
    }

    int** ans = multiple(num, p);

    for(int i = 0; i < psize; i++) {
        for(int j = 0; j < psize; j++)
            cout << ans[i][j] << " ";
        cout << endl;
    }
}