728x90

 0. [c++] 백준


https://www.acmicpc.net/problem/10830


 1. 풀이


이번 문제는 1629 - 곱셈문제와 상당히 유사하게 해결하였다.


원래 주어진 문제는 분할 정복을 하여서 풀어야 하였지만, 이 문제를 비트마스크를 활용하면 간단하게 풀 수 있을 것 같아서 이를 활용하였다.


시간 복잡도는 로 구현되었다.




 2. 소스코드


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
#include<iostream>
 
using namespace std;
 
typedef unsigned long long ull;
 
int N;
ull B;
int matrix[6][6];
int temp[6][6];
int cache[50][6][6];
bool visited[50];
int ret[6][6];
 
void calc() {
    int power = 0;
    while (B > 1) {
        //B를 2진수로 변환하여 변환되는 2진수 부분을 visited배열에 저장해주었다.
        if (B % 2)
            visited[power] = true;
 
        //temp행렬을 초기화해준다.
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                temp[y][x] = 0;
            }
        }
 
        //행렬을 2^power번 제곱한 값을 cache에 미리 저장 해주었다.(B의 크기가 100,000,000,000 이하이므로 power가 40을 넘지 않는다.)
        //행렬을 제곱한 값을 temp에 담아준다.
        for (int bra = 0; bra < N; bra++) {
            for (int ket = 0; ket < N; ket++) {
                for (int i = 0; i < N; i++) {
                    temp[bra][ket] += cache[power][bra][i] * cache[power][i][ket];
                    temp[bra][ket] %= 1000;
                }
            }
        }
 
        //지수를 증가시켜주고, cache에 temp의 값을 옮겨 담아주었다.
        power++;
        for (int y = 0; y < N; y++) {
            for (int x = 0; x < N; x++) {
                cache[power][y][x] = temp[y][x];
            }
        }
 
        B /= 2;
    }
    visited[power] = true;
 
    //ret행렬을 단위행렬로 만들어준다.
    for (int i = 0; i < N; i++) {
        ret[i][i] = 1;
    }
 
    for (int i = 0; i <= power; i++) {
        if (visited[i]) {
            //temp행렬을 초기화해준다.
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    temp[y][x] = 0;
                }
            }
 
            //ret과 cache를 곱해준다.
            for (int bra = 0; bra < N; bra++) {
                for (int ket = 0; ket < N; ket++) {
                    for (int j = 0; j < N; j++) {
                        temp[bra][ket] += ret[bra][j] * cache[i][j][ket];
                        temp[bra][ket] %= 1000;
                    }
                }
            }
            for (int y = 0; y < N; y++) {
                for (int x = 0; x < N; x++) {
                    ret[y][x] = temp[y][x];
                }
            }
        }
    }
 
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            cout << ret[y][x] << " ";
        }
        cout << "\n";
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> B;
    for (int y = 0; y < N; y++) {
        for (int x = 0; x < N; x++) {
            cin >> matrix[y][x];
            cache[0][y][x] = matrix[y][x];
        }
    }
 
    calc();
 
    return 0;
}
cs


 3. 참고



질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!


저작자표시

'<백준> > |c++| normal' 카테고리의 다른 글

[c++] 백준 15652 - N과 M(4) (백트래킹 대신 조건문 활용)  (0) 2020.01.10
[c++] 백준 15649 - N과 M (1) (백트래킹, dfs)  (0) 2019.09.19
[c++] 백준 1629 - 곱셈(분할 정복인데 비트마스크 활용?)  (0) 2019.08.29
[c++] 백준 17298 - 오큰수(스택)  (0) 2019.08.28
[c++]백준 2004 - 조합 0의 개수(수학, 빠르게 지수 구하기)  (0) 2019.08.27

+ Recent posts

티스토리툴바