글 읽기 - 메모리 초과가 납니다... 고수님들 도와주세요 ㅠㅠㅠ

pda_pro12 6년 전 0

왜 자꾸 메모리 초과가 발생하죠....ㅠㅠㅠ

이걸 어떻게 줄여야할지 도저히 모르겠습니다...! ㅠㅠㅠ

도와주세요 고수님들!

#include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std; 
#pragma warning(disable:4996)
int n;   int arr[100001][3]; int dp[100001][3]; int Max; int Min = 987654321;
int main()
{
	cin >> n; 
	for (int i = 1; i <= n; i++)     // 초기 배열 입력
		for (int j = 1; j <= 3; j++) 
			scanf("%d",&arr[i][j]);


	for (int i = 1; i <= n; i++) {   // 최대값 계산 과정
		dp[i][1] = max(dp[i - 1][1]+arr[i][1], dp[i-1][2]+arr[i][1]);
		dp[i][2] = max(max(dp[i - 1][1] + arr[i][2], dp[i - 1][2] + arr[i][2]),dp[i-1][3]+arr[i][2]);
		dp[i][3] = max(dp[i - 1][2] + arr[i][3], dp[i - 1][3] + arr[i][3]);
	}
	Max = max(max(max(dp[n][1], dp[n][3]), dp[n][2]), Max);  // 최대값 계산 

	for (int i = 1; i <= n; i++)    // dp배열 초기화
		for (int j = 1; j <= 3; j++) 
			dp[i][j] = 0; 

	for (int i = 1; i <= n; i++) {   // 최소값 계산 과정
		dp[i][1] = min(dp[i - 1][1] + arr[i][1], dp[i - 1][2] + arr[i][1]);
		dp[i][2] = min(min(dp[i - 1][1] + arr[i][2], dp[i - 1][2] + arr[i][2]), dp[i - 1][3] + arr[i][2]);
		dp[i][3] = min(dp[i - 1][2] + arr[i][3], dp[i - 1][3] + arr[i][3]);
	}

	Min = min(min(min(dp[n][1], dp[n][3]), dp[n][2]), Min);  // 최소값 계산
	cout << Max << " " << Min; 
	return 0; 
}

djm03178 6년 전 0

맞히신 것 같지만, 이 문제는 배열을 10만씩 선언할 필요가 없습니다. 사실, 4MB라는 메모리 제한이 좀 더 효율적으로 먹히려면 N이 50만쯤 되면 더 좋았을 거 같네요. 항상 현재 줄, 그 다음 줄에 대한 정보만 저장하고 있으면 되기 때문이죠. 이미 지나간 위쪽 부분이나 아직 닿지 않은 아랫쪽 부분은 담아둘 필요가 없습니다.

저는 현재줄에서 3개의 인덱스를 A,B,C라 하였을때 A를 선택하였을때 전줄에서 선택할수있는 인덱스 중 MAX 값을 현재 줄 DP배열에 저장하면서 N번째 줄까지 BOTTOM-UP하는 방식으로 진행하였습니다만, 그렇게 하지않으면 조금 많이 아래에 있는 행에서 기하급수적으로 큰수가 나온다고 가정하였을때, 지나간 줄에서 다른 인덱스를 선택하여야하는 케이스가 생기지 않을까요?

제 생각입니다만... ㅠㅠㅠ

djm03178 6년 전 0

궁금하시면 제 코드 https://www.acmicpc.net/source... 읽어보세요.

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

문제

문제

출처

ICPC

메모리 초과가 납니다... 고수님들 도와주세요 ㅠㅠㅠ

pda_pro12 6년 전 0

djm03178 6년 전 0

pda_pro12 6년 전 0

djm03178 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말