글 읽기 - 모든 테스트케이스는 나오는데 정답이 ㅠㅠ

revolution_2 5년 전 6

제출했을때 틀렸습니다가 나오는데...

분할 정복방법으로 접근했습니다.

아무리 찾아도 문제점을 잘 모르겠네요 ㅠㅠ

#include <iostream>
#include <vector>

using namespace std;

int N;
long long B;
int arr[6][6];

vector<vector<int>> mul(long long sq) {
    vector<vector<int>> ans(N, vector<int>(N));
    vector<vector<int>> c(N, vector<int>(N));

    if(sq == 1) {
        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < N; j ++) {
                c[i][j] = arr[i][j];
            }
        }

        return c;
    }
    // 제곱수가 짝수일때
    if(sq%2 == 0) {
        c = mul(sq/2);
        // c 배열의 제곱을 구함
        for(int i = 0; i < N; i ++) {
            for(int j = 0; j < N; j ++) {

                for (int k = 0; k < N; k ++) {
                    ans[i][j] += c[i][k] * c[k][j];
                }
                ans[i][j] %= 1000;
            }
        }

        return ans;
    } else {
        c = mul(sq-1);
        // c 배열에 arr을 곱합
        for (int i = 0; i < N; i ++) {
            for (int j = 0; j < N; j ++) {

                for (int k = 0; k < N; k ++) {
                    ans[i][j] += c[i][k] * arr[k][j];
                }
                ans[i][j] %= 1000;
            }
        }
        return ans;
    }
}

int main() {
    cin >> N >> B;

    vector<vector<int>> ans(N, vector<int>(N));

    for(int i = 0; i < N; i ++) {
        for (int j = 0; j < N; j ++) {
            cin >> arr[i][j];
        }
    }

    ans = mul(B);

    for(int i = 0; i < N; i ++) {
        for (int j = 0; j < N; j ++) {
            cout << ans[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}