반응형

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

 

17401번: 일하는 세포

출력은 N개의 줄로 구성되며, i 번째 줄에는 N개의 정수 xi1, xi2, ..., xiN를 공백으로 구분하여 출력해야 한다. xij는 0초 때 거점 i 에서 출발하여 정확히 D초 때 거점 j에 위치하게 되는 경로의 수를 1

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다!

https://rudalsd.tistory.com/38

 

[ 백준 ] 12850번 - 본대 산책2 (C++)

https://www.acmicpc.net/problem/12850 12850번: 본대 산책2 가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net [ 문제풀이 ] 준영이가 정보관에서 1분 후 이동할 수 있는 건물은 전..

rudalsd.tistory.com

 

위 글의 문제 풀이 방식과 매우 비슷하지만 행렬이 매번 바뀌고, 바뀐 행렬에 따라 풀이 방법이 달라집니다.

 

1. 각각의 행렬을 모두 곱한 all 행렬과 나머지 행렬들을 곱한 remain 행렬을 만듭니다.

 

2. 분할 정복을 통해 구한 ans와 remain 행렬을 곱합니다.

 

[ 소스 코드 ]

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
#include<iostream>
#include<vector>
#include<unordered_map>
 
#define ll long long
#define M 1000000007
 
using namespace std;
 
int T, N, D;
 
vector<vector<int>> all(21, vector<int>(21, 0));    //모든 행렬을 곱한 행렬
unordered_map<int, vector<vector<int>>> m;        //메모제이션
 
vector<vector<int>> matrix(vector<vector<int>> arr1, vector<vector<int>> arr2)    //행렬 곱
{
    vector<vector<int>> ret(N + 1, vector<int>(N + 1, 0));
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            ll sum = 0;
            for (int k = 1; k <= N; k++) {
                sum += (((ll)arr1[i][k]%M) * ((ll)arr2[k][j]%M))%M;
                sum %= M;
            }
            ret[i][j] = sum%M;
        }
    }
 
    return ret;
}
 
vector<vector<int>> conquer(int num)        //분할 정복
{
    if (num == 1) {
        return all;
    }
    if (!m[num].empty()) {
        return m[num];
    }
 
    if (num % 2 == 0) {
        return m[num] = matrix(conquer(num / 2), conquer(num / 2));
    }
    else {
        return m[num] = matrix(conquer(num - 1), conquer(1));
    }
}
 
int main()
{
    scanf("%d %d %d", &T, &N, &D);
 
    vector<vector<int>> remain(N + 1, vector<int>(N + 1, 0));    //나머지 행렬들의 곱
    vector<vector<int>> ans(N + 1, vector<int>(N + 1, 0));        //답
 
    for (int i = 1; i <= N; i++) {    //단위 행렬로 초기화
        all[i][i] = 1;
        ans[i][i] = 1;
    }
 
    int d = D % T;    //남은 행렬들의 수
 
    for (int i = 0; i < T; i++) {
        int m, a, b, c;
        scanf("%d", &m);
        vector<vector<int>> temp(N + 1, vector<int>(N + 1, 0));
 
        for (int j = 0; j < m; j++) {
            scanf("%d %d %d", &a, &b, &c);
            temp[a][b] = c;    //i번 째 행렬
        }
        if (i == d) {    //나머지 행렬
            remain = all;
        }
        all = matrix(all, temp);
    }
 
    if (D / T != 0) {    //모든 행렬들이 곱해진 행렬이 곱해지는 횟수
        ans = conquer(D / T);
        
    }
 
    ans = matrix(ans, remain);
    
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            printf("%d ", ans[i][j]);
        }
        printf("\n");
    }
}
cs
반응형
저작자표시 비영리 변경금지

'백준' 카테고리의 다른 글

[ 백준 ] 9465번 - 스티커 (C++)  (0) 2022.08.12
[ 백준 ] 1932번 - 정수 삼각형 (C++)  (0) 2022.08.11
[ 백준 ] 14942번 - 개미 (C++)  (0) 2022.08.09
[ 백준 ] 13141번 - Ignition (C++)  (0) 2022.08.08
[ 백준 ] 7578번 - 공장 (C++)  (0) 2022.08.07

+ Recent posts

티스토리툴바