글 읽기 - 런타임문제인데 단순 long long에서 int파싱 문제인지 정확히 모르겠습니다.

2015136077 4년 전 0

코드상에서 런타임의 문제가 날 곳은 제 생각에는 파싱문제인데 파싱도 어디가 문제인지 모르겠습니다. 혹시 또 다른 문제가 있을까요

이유를 정확히 모르겠습니다.

#include <iostream>
#include <vector>

int n;
long long b;
std::vector< std::vector<long long> >data;
std::vector< std::vector< std::vector<long long> > >dp;

//백준 10830 (행렬의 b제곱을 구한다음 1000으로 나눈 값을 보여주는 방식)
//2로 나눈 값을 계속 찾아가는 방식
//64이면 32 16 8 4 2 이런식으로 제곱을 dp하여 계산(홀수일때는 한번 더 곱함.)
void multiply(int x, int y) {//행렬 곱셈을 수행하는 함수

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				dp[x + y][i][j] += dp[x][i][k] * dp[y][k][j];
			}
		}
	}
}

void calculate(int n, long long b) {//재귀적으로 행렬의 곱을 구하는 식
	if (b == 1) {
		dp[1] = data;
		return;
	}
	if ((b % 2 == 1)) {
		calculate(n, b / 2);
		multiply(b / 2, b / 2);
		multiply(b - 1, 1);
	}
	else {
		calculate(n, b / 2);
		multiply(b / 2, b / 2);
	}
}

//assign을 통해 할당하면 2중벡터 사이즈를 간단하게 할 수 있음
int main() {
	
	scanf("%d %lli", &n, &b);
	data.assign(n, std::vector<long long>(n));
	dp.assign(b+1, data);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			scanf("%lli", &data[i][j]);
		}
	}
	calculate(n,b);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			printf("%d ", dp[b][i][j]%1000);
		}
		printf("\n");
	}


}

djm03178 4년 전 0

b+1개의 data를 assign하려면 메모리가 얼마나 필요할까요?

2015136077 4년 전 0

잘 이해가 가지않습니다. long long의 데이터 값을 가지는 벡터가 최대 100,000,000,000+1개까지 필요하니 그 값이 너무 커 오버된다는 의미인가요? 만약 그렇다면 저 알고리즘은 절대 수정해서 사용이 불가능하다는 의미인 것 같은데 잘 모르겠네요

djm03178 4년 전 1

그렇습니다. 1000억이면 개당 8바이트씩이어도 800GB의 메모리를 필요로 하는데다가 실제 크기는 개당 n*n씩 곱해지는데 , 문제의 메모리 제한을 한참 뛰어넘을 뿐만 아니라 아예 할당조차 가능할 리가 없습니다.

2015136077 4년 전 0

결국엔 다른분들이 하신 알고리즘을 쓰는 방법밖에는 없겠네요 ㅠ 감사합니다

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

문제

문제

출처

ICPC

런타임문제인데 단순 long long에서 int파싱 문제인지 정확히 모르겠습니다.

2015136077 4년 전 0

djm03178 4년 전 0

2015136077 4년 전 0

djm03178 4년 전 1

2015136077 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말