글 읽기 - 메모리초과 질문입니다

ahj1592 4년 전 0

Aⁿ을 구하는 로직은

n이 짝수일때, A^n/2 * A^n/2

n이 홀수일때, A^(n-1)/2 * A^(n-1)/2 *A 로 나누어서 풀었습니다

행렬곱셈함수MatMtp()를 호출할때마다 C를 동적할당하여 풀었습니다

어느부분이 메모리초과에 기여(?) 하는지 잘 몰라서 질문드립니다

* 사실 시간초과도 나올것같은데 메모리초과 메시지가 먼저 나와 시간초과인지는 확실하지 않습니다

#include <stdio.h>
#include <stdlib.h>

int N, n;
int **A, **M;


int** MatMtp(int **A, int **B) {
	// return C = A*B
	int **C;
	C = (int **)malloc(sizeof(int *)*N);
	for (int i = 0; i < N; i++)
		C[i] = (int *)malloc(sizeof(int)*N);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			C[i][j] = 0;
			for (int k = 0; k < N; k++)
				C[i][j] += A[i][k] * B[k][j];
			C[i][j] = C[i][j] % 1000;
		}
		
	}
	
	return C;
}

int** MatN(int **A,int n) {
	// return A^n

	int **R;
	
	if (n == 1)
		return R = A;
	else if (n == 2)
		return R = MatMtp(A, A);
	else if (n % 2 == 0) 
		return R = MatMtp(MatN(A, n / 2), MatN(A, n / 2));
	else 
		return R = MatMtp(A, MatMtp(MatN(A, (n - 1) / 2), MatN(A, (n - 1) / 2)));
	
		

}

int main() {
	//freopen("input.txt", "r", stdin);

	scanf("%d %d", &N, &n);

	// memory allocation, input matrix
	A = (int **)malloc(sizeof(int *)*N);
	for (int i = 0; i < N; i++)
		A[i] = (int *)malloc(sizeof(int)*N);


	// input A[i][j]
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			scanf("%d", &A[i][j]);
			if (A[i][j] >= 1000)
				A[i][j] = A[i][j] % 1000;
		}
			
	}
	printf("input complete\n");

	M = MatN(A, n);

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
			printf("%d ", M[i][j]);
		printf("\n");
	}

	return 0;
}

pichulia 4년 전 0

free 라는 함수를 아십니까

ahj1592 4년 전 0

(66번째줄은 주석처리하였습니다)

죄송하지만 free함수를 어디서 사용해야할지 모르겠습니다

main에서 행렬 M 을 다 출력하고나서 A를 free 해보았지만 소용이없습니다ㅠㅠ

pichulia 4년 전 0

MatMtp 함수 내부에서 메모리를 할당한 C라는 녀석을 free해야합니다.

근데 이 친구가MatN 내부에서 사용되기 때문에 함부로 free를 할 수가 없는 골때리는 상황이군요ㅋㅋㅋ 어떻게 해결해야할지 고민해봅시다.ㅋㅋ

해결 방법이 여러가지 있겠지만...저였다면 일단 34번째 줄에 대해선 R=A가 아니라 R에 malloc을 해서 A의 값을 복사했을 것입니다.

pichulia 4년 전 0

그리고 이건 저도 지금 제출해봐서 알았는데... n(소문자 n)의 값의 범위가 int범위를 넘어가기 때문에 long long int를 사용해야합니다. ㅠㅠ

ahj1592 4년 전 0

그냥 함수를 새로 만들어서 풀었습니다

원래대로하면 함수호출이 많아져서 메모리초과가 나는것같더군요

1) 행렬2개곱하는함수

2) 행렬을 제곱하는함수

이렇게 만들어서

n이 짝수 -> A^n/2를 제곱

n이홀수 -> A * A^n-1 곱하기

이렇게 하니까 해결했습니다

그리고 n이 long long 인것도 감사합니다!!!

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

문제

문제

출처

ICPC

메모리초과 질문입니다

ahj1592 4년 전 0

pichulia 4년 전 0

ahj1592 4년 전 0

pichulia 4년 전 0

pichulia 4년 전 0

ahj1592 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말