행렬의 곱2 백준(BOJ) 13328 Message Passing * # 수학우선 수가 크기 때문에 dp로도 안풀린다.-> logn으로 해결해야한다.수학 행렬을 사용하면 된다. 이 문제를 풀기 전에 피보나치수3을 푸는것을 추천한다.https://www.acmicpc.net/problem/2749 피보나치 수은 이전의 2개를 더한다면이번 문제에서는 이전의 d개의 수를 더해주면 된다. 여기서 기존의 d=2 기존의 피보나치의 수와 같은 행렬의 제곱으로 해결할 수 있고d>2의 경우, 다음과 같이 해결이 된다. #include #include #include #include #include #include #include #include #include #define MAX 1005 #define INF 987654321 #define MOD 31991 #pragma warning.. 2018. 8. 11. [알고리즘] 구조체를 이용한 행렬의 곱 구현 크기가 d인 행렬(d*d)의 곱 a*b를 구하는 코드 실행 코드 #include #pragma warning(disable:4996) using namespace std; int d; struct st { int m[55][55] = {}; st operator*(st a) const { st ret; for (int i = 0; i < d; i++) for (int j = 0; j < d; j++) for (int k = 0; k < d; k++) ret.m[i][j] = (ret.m[i][j] + m[i][k] * a.m[k][j]); return ret; } }a,b,c; int main() { d=3; for(int i=0;i 2018. 8. 11. 이전 1 다음
