글 읽기 - 메모리 초과는 해결하였습니다. 그러나 반례를... ㅠ

kim031504 4년 전 0

기존에 DP를 위한 10만 행짜리 2차원 배열을 이용하지 않고,

값을 갱신해 나갈 때, 단 2개의 행만 이용합니다.

즉, 현재 행의 값을 계산할 때에는 이전에 구했던 DP 값과 사용자로부터 입력받은 현재의 배열 A만 필요합니다.

그래서 크기가 3인 1차원 배열 여러개를 이용해서 풀었습니다.

계산하면 메모리 초과는 일어나지 않습니다.

하지만, 틀리네요... ㅠ 반례를 못 찾겠습니다 ㄷㄷ

코드의 자세한 설명은 주석으로 달아놨습니다!

#include <iostream>
#include <algorithm>

using namespace std;

/*
	A : 값을 입력받기 위한 배열
	preDPMAX : 이전 행의 최대 DP 저장 값을 참조
	curDPMAX : preDPMAX와 A를 이용해 현재 계산해야 할 최대 DP를 담는다.
	preDPMIN : 이전 행의 최소 DP 저장 값을 참조
	curDPMIN : preDPMIN와 A를 이용해 현재 계산해야 할 최소 DP를 담는다.

*/

int A[3] = { 0, }, 
    preDPMAX[3] = { 0, }, 
    curDPMAX[3] = { 0, }, 
    preDPMIN[3] = { 0, }, 
    curDPMIN[3] = { 0, };

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < 3; j++)
		{
			// 첫 번째 행이라면
			if (i == 0)
			{
				cin >> A[j];

				preDPMAX[j] = A[j];
				preDPMIN[j] = A[j];
			}
			else
			{
				cin >> A[j];
			}
		}

		// 둘째 행부터 현재 입력받은 A와 이전 pre DP를 이용해 연산할 수 있다.
		if (i >= 1)
		{

			curDPMAX[0] = max(preDPMAX[0], preDPMAX[1]) + A[0];
			curDPMAX[1] = max(max(preDPMAX[0], preDPMAX[1]), preDPMAX[2]) + A[1];
			curDPMAX[2] = max(preDPMAX[2], preDPMAX[1]) + A[2];

			curDPMIN[0] = min(curDPMIN[0], curDPMIN[1]) + A[0];
			curDPMIN[1] = min(min(curDPMIN[0], curDPMIN[1]), curDPMIN[2]) + A[1];
			curDPMIN[2] = min(curDPMIN[2], curDPMIN[1]) + A[2];

			// cur DP 연산 수행 후 pre DP 배열에 덮어씌운다. 그래야 다음 단계 진행 가능!
			for (int j = 0; j < 3; j++)
			{
				preDPMAX[j] = curDPMAX[j];
				preDPMIN[j] = curDPMIN[j];
			}
		}
	}

	// 최대 / 최소 출력!
	cout << *max_element(preDPMAX, preDPMAX + 3) << ' '
		<< *min_element(preDPMIN, preDPMIN + 3) << '\n';

	return 0;
}

trimind 4년 전 0

input:
2
1 2 3
1 2 3

output:
6 1

solution:
6 2

curDPMAX계산할 땐 preDPMAX를 이용해서 계산하시는데, curDPMIN 계하실땐 curDPMIN를 이용하시네요

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

문제

문제

출처

ICPC

메모리 초과는 해결하였습니다. 그러나 반례를... ㅠ

kim031504 4년 전 0

trimind 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말