반응형
https://www.acmicpc.net/problem/12850
12850번: 본대 산책2
가능한 경로의 수를 1,000,000,007로 나눈 나머지를 출력한다.
www.acmicpc.net
[ 문제풀이 ]
준영이가 정보관에서 1분 후 이동할 수 있는 건물은 전산관과 미래관입니다. 또한 전산관에서 1분 후 이동할 수 있는 건물은 신양관, 미래관 그리고 정보관입니다. 이를 행렬로 표현하면 다음과 같습니다.
그렇다면 각 건물에서 2분 후 이동할 수 있는 건물은 어떻게 구할 수 있을까요? 바로 1분 후 이동할 수 있는 건물들에 대한 행렬을 서로 곱하면 됩니다.
따라서 n분 후 이동할 수 있는 건물을 구하는 방법은 다음과 같습니다.
n % 2 == 0 일 때
mat( n / 2 ) * mat( n / 2 )
n % 2 == 1 일 때
mat( n - 1 ) * mat( 1 )
재귀를 통해 D번 이동했을 때 mat( D )의 0 , 0의 값을 출력하면 정보과학관으로 돌아오는 경우의 수를 구할 수 있습니다.
[ 소스 코드 ]
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 | #include <iostream> #include <vector> #include <unordered_map> #define ll long long using namespace std; vector<vector<ll>> mat = { //연결되어 있으면 1 {0,1,1,0,0,0,0,0}, {1,0,1,1,0,0,0,0}, {1,1,0,1,1,0,0,0}, {0,1,1,0,1,1,0,0}, {0,0,1,1,0,1,1,0}, {0,0,0,1,1,0,0,1}, {0,0,0,0,1,0,0,1}, {0,0,0,0,0,1,1,0} }; int D; ll MOD = 1000000007; unordered_map<int, vector<vector<ll>>> m; vector<vector<ll>> multi(vector<vector<ll>> A, vector<vector<ll>> B) //A, B 행렬 곱 { vector<vector<ll>> ret; for (int i = 0; i < 8; i++) { vector<ll> tmp; for (int j = 0; j < 8; j++) { ll sum = 0; for (int k = 0; k < 8; k++) { sum += A[i][k] * B[k][j]; sum %= MOD; } tmp.push_back( sum ); } ret.push_back( tmp ); } return ret; } vector<vector<ll>> dfs(int num) //행렬을 num번 곱했을 때 배열 { if (m.find(num) != m.end()) { return m[num]; } if (num % 2 == 0) { return m[num] = multi(dfs(num / 2), dfs(num / 2)); } else { return m[num] = multi(dfs(num - 1), dfs(1)); } } int main() { cin >> D; m[1] = mat; dfs(D); cout<<m[D][0][0]; } | cs |
반응형
'백준' 카테고리의 다른 글
| [ 백준 ] 2568번 - 전깃줄 - 2 (C++) (0) | 2022.06.25 |
|---|---|
| [ 백준 ] 14939번 - 불 끄기 (C++) (0) | 2022.06.24 |
| [ 백준 ] 2098번 - 외판원 순회 (C++) (0) | 2022.06.22 |
| [ 백준 ] 14003번 - 가장 긴 증가하는 부분 수열 5 (C++) (0) | 2022.06.21 |
| [ 백준 ] 9328번 - 열쇠 (C++) (0) | 2022.06.20 |