글 읽기 - 제 코드의 문제점을 알고싶습니다.

cocoon 3년 전 0

분할정복으로 로직은 맞게 짠거같은데 B가 3이상 일때 모든값이 0으로 출력됩니다.

예를들어

print_arr(Matrix_multi(A, solve(A, 1))); ==> A*A 까지는 정확하게 출력되는데

print_arr(Matrix_multi(A, solve(A, 2))); ==> A*A*A 부터는 모든값이 0이 출력됩니다.

즉, print_arr(Matrix_multi(A, Matrix_multi(A, A))); 에서부터 문제가 발생하는것 같습니다.

( print_arr(Matrix_multi(A, A));는 잘 출력됩니다. )

2차원 배열을

int(*Matrix_multi(int X[5][5], int Y[5][5]))[5]

이런식으로 리턴하면 안되는 것인지 뭐가 문제인지 몰라서 도움을 요청드리려 글 올립니다 ㅜㅜ

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

int N, B;
int A[5][5];
int Z[5][5];

// 배열 출력
void print_arr(int arr[5][5])
{
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
			cout << arr[i][j] << " ";
		cout << endl;
	}
}

// 행렬 곱셈
int(*Matrix_multi(int X[5][5], int Y[5][5]))[5]
{
	// Z배열 초기화
	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			Z[i][j] = 0;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
		{
			for (int k = 0; k < N; k++)
				Z[i][j] += (X[i][k] * Y[k][j]) % 1000;
			
			Z[i][j] = Z[i][j] % 1000;
		}
		
	return Z;
}

// 분할 정복
int (*solve(int arr[5][5], int size))[5]
{
	if (size == 1) return A;
	
	if (size % 2 == 1) 
	{
		return Matrix_multi(A, solve(A, size - 1));
	}
	else
	{
		return Matrix_multi(solve(A, size / 2), solve(A, size / 2));
	}
	
}

int main()
{
	cin >> N >> B;

	for (int i = 0; i < N; i++)
		for (int j = 0; j < N; j++)
			cin >> A[i][j];
	
	print_arr(solve(A, B)); // A를 B번 곱한 결과

}

bupjae 3년 전 0

Matrix_multi(A, Matrix_multi(A, A)) 에서 문제가 발생하는 이유는 다음과 같습니다

편의상 Matrix_multi2(A, Matrix_multi1(A, A)) 로 구분해서 설명하겠습니다.

Matrix_multi1(A, A) 는 올바른 값을 계산하며, 결과로 Z 를 반환합니다.

그 뒤 Matrix_multi2(A, Z) 를 호출하게 되는데

25~27번째 줄에서 Z배열을 0으로 초기화해 버립니다.

즉, Matrix_multi2(A, Z) 는 결국 Matrix_multi(A, 0) 이 되어버리면서, 결과가 0배열이 됩니다.

cocoon 3년 전 0

앗! 그렇군요 성의있게 알려주셔서 정말 감사드립니다 ㅜㅜ

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

문제

문제

출처

ICPC

제 코드의 문제점을 알고싶습니다.

cocoon 3년 전 0

bupjae 3년 전 0

cocoon 3년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말