백준 2096번: 내려가기

[문제 링크]

2096번: 내려가기

---

필자는 처음 풀 때 배열 크기를 arr[100000][3]으로 잡고 풀었는데, 메모리초과를 받았다.

다른 사람의 코드를 찾아봤는데 이유는 모르겠지만 배열 크기를 arr[100000][3] 으로 잡고도 정답을 받은 사람들이 많이 있었다.

분명 코드가 똑같은데 메모리초과를 받길래 계속 고민해봤지만 해답을 찾을 수 없었다. 아마도 입출력부분에서 메모리차이가 났던거 같다.

그러던중 N이 최대 100000이라고 해서 배열 크기를 100000으로 잡을 필요가 없다라는 힌트를 보고 정답을 받을 수 있었다. 문제 출제자의 출제 의도도 이쪽에 더 가깝다고 생각한다.

---

#include <iostream>
using namespace std;

int memoMin[3];
int memoMax[3];

int max(int a, int b) { return a > b ? a : b; }
int min(int a, int b) { return a < b ? a : b; }

int main(void)
{
	int N;
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		if (i == 0)
		{
			memoMin[0] = memoMax[0] = a;
			memoMin[1] = memoMax[1] = b;
			memoMin[2] = memoMax[2] = c;
		}
		else
		{
			int tempA, tempB, tempC;

			tempA = memoMin[0], tempB = memoMin[1], tempC = memoMin[2];

			memoMin[0] = min(tempA, tempB) + a;
			memoMin[1] = min(tempA, min(tempB, tempC)) + b;
			memoMin[2] = min(tempB, tempC) + c;

			tempA = memoMax[0], tempB = memoMax[1], tempC = memoMax[2];

			memoMax[0] = max(tempA, tempB) + a;
			memoMax[1] = max(tempA, max(tempB, tempC)) + b;
			memoMax[2] = max(tempB, tempC) + c;



		}
	}

	int minVal = min(memoMin[0], min(memoMin[1], memoMin[2]));
	int maxVal = max(memoMax[0], max(memoMax[1], memoMax[2]));

	cout << maxVal << ' ' << minVal << endl;

	return 0;
}

알고리즘 200일 프로젝트 - 94 day