글 읽기 - 메모리초과?? 왜죠??

xowns9418 6년 전 0

배열의 열의 갯수를 N의 최대범위인 100000까지 할당할 필요 없이 열의 갯수 2개로 문제를 해결하긴 했지만 제가 맨처음 시도한 아래 소스가 왜 메모리 초과가 발생하는지 궁금해서 질문드립니다. 제 생각에는 아래 소스의 메모리 사용은 (4*100000*3*3)/1024/1024 = 3.4MB 정도 된다고 생각됩니다. 그러나, 문제의 메모리제한은 4MB인데 왜 메모리 제한이 발생하는 건가요??

#include<iostream>
#include<algorithm>
using namespace std;
#define MAX_SIZE 100000
#define INF 987654321

int map[MAX_SIZE][3];
int dp_max[MAX_SIZE][3]; //제일 윗줄에서 (i, j)로 올 때의 최대 점수
int dp_min[MAX_SIZE][3]; //제일 윗줄에서 (i, j)로 올 떄의 최소 점수

int main(void) {

	ios_base::sync_with_stdio(false);
	int n;
	cin >> n;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			cin >> map[i][j];
		}
	}

	for (int i = 0; i < 3; i++) {
		dp_max[0][i] = dp_min[0][i] = map[0][i];
	}

	for (int i = 1; i < n; i++) {
		for (int j = 0; j < 3; j++) {
			if(j == 0) {
				dp_min[i][j] = min(dp_min[i - 1][j], dp_min[i - 1][j + 1]) + map[i][j];
				dp_max[i][j] = max(dp_max[i - 1][j], dp_max[i - 1][j + 1]) + map[i][j];
			}
			else if (j == 2) {
				dp_min[i][j] = min(dp_min[i - 1][j], dp_min[i - 1][j - 1]) + map[i][j];
				dp_max[i][j] = max(dp_max[i - 1][j], dp_max[i - 1][j - 1]) + map[i][j];
			}
			else {
				dp_min[i][j] = min({ dp_min[i - 1][j], dp_min[i - 1][j - 1], dp_min[i-1][j+1] }) + map[i][j];
				dp_max[i][j] = max({ dp_max[i - 1][j], dp_max[i - 1][j - 1], dp_max[i-1][j+1] }) + map[i][j];
			}
		}
	}

	int MIN = INF;
	int MAX = 0;

	for (int i = 0; i < 3; i++) {
		MIN = min(MIN, dp_min[n-1][i]);
		MAX = max(MAX, dp_max[n-1][i]);
	}

	cout << MAX << " " << MIN;

	return 0;
}

chogahui05 6년 전 0

이 글 참고하세요.

http://stackoverflow.com/quest...

sizeof(int)의 값이 항상 4가 아닙니다. 환경에 따라서 달라질 수 있습니다.

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

문제

문제

출처

ICPC

메모리초과?? 왜죠??

xowns9418 6년 전 0

chogahui05 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말