글 읽기 - 10830 시간 초과 질문 드립니다 두개의 코드 비교 부탁드립니다.

axa1239 4년 전 1

읽어 주셔서 감사합니다

우선 해결 방식으로는 분할 정복으로써 해결 하였습니다.

두개의 코드 모두 분할 정복 방식이지만 코드를 조금 수정 하여 시간 초과를 피할 수 있었습니다.

오버라이딩을 통하여 행렬의 곱셈을 정의 하였고 곱한 결과를 반환 하게 구성 하였습니다.

cal 함수 - > 분할 정복 방식으로 행렬의 곱셈을 처리 하였습니다.

밑에 소스 코드와 같이 cal1은 시간 초과를 받은 코드이고 cal2 는 통과한 코드 입니다

도대체 어떤 부분에서 시간이 걸리는지 이해가 가질 않습니다 고수분들 도와주세요!!

matrix cal1(matrix a, ll m) {
	if (m == 1) return a;
	if (m % 2 == 1) return	cal(a, m - 1) * a;
	else return cal(a, m / 2) * cal(a, m / 2);
}

matrix cal2(matrix a, ll m) {
	matrix ans(n, vector<int>(n)); 
	for (int i = 0; i < n; i++) ans[i][i] = 1; 
	if (m == 0) return ans;
	if (m % 2) ans = ans * a; return ans * cal(a * a, m / 2);
}


#include <iostream>
#include <algorithm>
#include <vector>
#define MOD 1000
using namespace std;
typedef long long ll;
int n;
typedef vector<vector<int>> matrix;
matrix operator*(const matrix& a, const matrix& b) {
	matrix res(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int sum = 0;
			for (int k = 0; k < n; k++) {
				sum += ((a[i][k] * b[k][j])) % MOD;
			}
			res[i][j] = sum % MOD;
		}
	}
	return res;
}
/*
matrix cal(matrix a, ll m) {
	if (m == 1) return a;
	if (m % 2 == 1) return	cal(a, m - 1) * a;
	else return cal(a, m / 2) * cal(a, m / 2);
}
*/

matrix cal(matrix a, ll m) {
	matrix ans(n, vector<int>(n)); 
	for (int i = 0; i < n; i++) ans[i][i] = 1; 
	if (m == 0) return ans;
	if (m % 2) ans = ans * a; return ans * cal(a * a, m / 2);
}
int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	ll m;
	cin >> n >> m;
	matrix a(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> a[i][j];
		}
	}
	auto ans = cal(a, m);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << ans[i][j] << ' ';
		}
		cout << '\n';
	}
	cout << '\n';
	return 0;
}

herdson 4년 전 1

4번째 줄에 문제가 있습니다.

왜냐하면 전처리가 안되고 재귀를 돌리므로 결국엔 logn번 제곱하는게 아니라 n번 제곱하는 것과 동일해집니다.

행렬에서 큰 수 제곱을 제대로 구현하기 위해서는 11번째 줄처럼 다음 재귀로 넘어가기전 사전에 n * n의 결과를 계산하고 이를 인자로 넘겨주어야 합니다.

axa1239 4년 전 0

아.... 꽉 막히던게 이제야 이해가 갑니다

정말 감사드립니다.

결국에는 return cal(a, m / 2) * cal(a, m / 2) 부분에서

cal 2번 호출이 되어서 n번 제곱하는것 과 같다 이 말씀이신거죠?

감사합니다!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

herdson 4년 전 1

네 맞습니다. 잘 이해하셨습니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

10830 시간 초과 질문 드립니다 두개의 코드 비교 부탁드립니다.

axa1239 4년 전 1

herdson 4년 전 1

axa1239 4년 전 0

herdson 4년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말