글 읽기 - 메모리초과때문에 빡돌기 일부직전이네요 고수님들 제발 도와주세요

tddhot2 7년 전 0

4MB이하 제약조건이 있어서 계산해봤습니다.

반복문으로 풀어야지 변수를 재활용할 수 있어서 그렇게 했습니다.

크게 메모리를 쓰는건 처음 입력받는 데이터들의 벡터 2차원배열하나입니다!!!!

100,000행 * 3열 * 4byte(int자료형) 이라서 계산해보면

총 1200000바이트 => 1.2메가바이트입니다 (구글 바이트 변환기로 했어요)

그럼 4MB는 안넘는 것인데!!!!

정답은 확실히 나오고있거든요 ㅠㅠ;;

도대체 왜 안되는지 모르겠습니다

이것때메 지금 5시간째 새벽까지 이러고 잇네요 ㅠㅠ

도와주십쇼 고수님들

#include "stdafx.h"
#include <iostream>
#include <vector>
#pragma warning(disable:4996)
using namespace std;

int main()
{
	int N; //내려갈 수 있는 행의 길이
	cin >> N;

	vector<vector<int>> Map(N, vector<int>(3, 0));

	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < 3; j++)
			cin >> Map[i][j];


	int a = Map[N-1][0];
	int b = Map[N - 1][1];
	int c = Map[N - 1][2];

	for (int i = N - 2; i >= 0; i--)
	{
		int tempA(0), tempB(0), tempC(0);
		if (Map[i][0] + a > Map[i][0] + b)
			tempA = Map[i][0] + a;
		else
			tempA = Map[i][0] + b;

		if (Map[i][1] + a > Map[i][1] + b)
		{
			if (Map[i][1] + a > Map[i][1] + c)
				tempB = Map[i][1] + a;
			else
				tempB = Map[i][1] + c;
		}
		else
		{
			if (Map[i][1] + b > Map[i][1] + c)
				tempB = Map[i][1] + b;
			else
				tempB = Map[i][1] + c;
		}

		if (Map[i][2] + b > Map[i][2] + c)
			tempC = Map[i][2] + b;
		else
			tempC = Map[i][2] + c;

		a = tempA;
		b = tempB;
		c = tempC;
	}

	int Max = a;
	if (Max < b)
		Max = b;
	if (Max < c)
		Max = c;


	a = Map[N - 1][0];
	b = Map[N - 1][1];
	c = Map[N - 1][2];

	for (int i = N - 2; i >= 0; i--)
	{
		int tempA(0), tempB(0), tempC(0);
		if (Map[i][0] + a < Map[i][0] + b)
			tempA = Map[i][0] + a;
		else
			tempA = Map[i][0] + b;

		if (Map[i][1] + a < Map[i][1] + b)
		{
			if (Map[i][1] + a < Map[i][1] + c)
				tempB = Map[i][1] + a;
			else
				tempB = Map[i][1] + c;
		}
		else
		{
			if (Map[i][1] + b < Map[i][1] + c)
				tempB = Map[i][1] + b;
			else
				tempB = Map[i][1] + c;
		}

		if (Map[i][2] + b < Map[i][2] + c)
			tempC = Map[i][2] + b;
		else
			tempC = Map[i][2] + c;

		a = tempA;
		b = tempB;
		c = tempC;
	}


	int Min = a;
	if (Min > b)
		Min = b;
	if (Min > c)
		Min = c;

	cout << Max << " " << Min << endl;

    return 0;
}

3587jjh 7년 전 1

헤더파일도 몇메가 할걸요..?

crasy111 7년 전 0

i번째줄을 계산할때는 i-1번째 줄만 필요하다는 특성을 이용해보세요

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

문제

문제

출처

ICPC

메모리초과때문에 빡돌기 일부직전이네요 고수님들 제발 도와주세요

tddhot2 7년 전 0

3587jjh 7년 전 1

crasy111 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말