백준 2096 c++ "내려가기" -PlusUltraCode-

https://www.acmicpc.net/problem/2096

 

[필자 사고]
처음에 필자는 N의 크기에 따라 열의 크기도 변하는 줄 알았다.

정답은 당연히 틀렸다.

두번째로 행의 크기만 변한다는걸 알고 열의 크기는 3으로 고정하고 2차원 배열 형태로 풀었따.

다만 메모리 초과 문제를 마지했다.

생각해보니 이전 값들은 필요가 없다. 현재가 중요하다.

그래서 maxDp, minDp 등등을 2차원 배열에서 1차원배열로 만들고 크기를 3으로 했다.

그런데 또 메모리 초과 문제를 맞이했다.... 

입력 배열 또한 2차원으로 되어있어 1차원으로 줄였떠니 문제를 해결할 수 있었다.

메모리에 대해서 깊이 고민해 봤던 문제다.

아래는 자세한 코드 해설이다.

[코드 해설]

2. 입력 처리 (Input 함수)

cpp

복사편집

void Input() { cin >> N; arr.resize(3); minDp.resize(3, 999999); maxDp.resize(3, -1); }

• N을 입력받아 보드의 행 개수를 설정한다.
• arr 벡터는 각 행의 3개의 값을 저장하는 용도로 사용된다.
• minDp는 최소 점수를 저장하는 배열로, 초기값을 큰 값(999999)으로 설정하여 비교를 용이하게 한다.
• maxDp는 최대 점수를 저장하는 배열로, 초기값을 작은 값(-1)으로 설정한다.

---

3. 게임 진행 (Game_Start 함수)

 

void Game_Start() { for (int i = 0; i < 3; i++) { cin >> arr[i]; } for (int i = 0; i < 3; i++) { minDp[i] = arr[i]; maxDp[i] = arr[i]; }

• 첫 번째 행을 입력받아 arr에 저장한다.
• minDp와 maxDp를 arr 값으로 초기화한다. 이는 첫 번째 행의 값이 그대로 첫 번째 DP 값이 되기 때문이다.

 

for (int i = 1; i < N; i++) { cin >> arr[0] >> arr[1] >> arr[2];

• 두 번째 행부터 N개의 행을 차례로 입력받아 처리한다.

3.1 최소 점수 갱신

 

int leftNum = minDp[0]; int midNum = minDp[1]; int rightNum = minDp[2]; minDp[0] = min(leftNum, midNum) + arr[0]; minDp[2] = min(rightNum, midNum) + arr[2]; minDp[1] = min(min(leftNum, midNum), rightNum) + arr[1];

• 이전 행(minDp)의 값을 leftNum, midNum, rightNum 변수에 저장한다.
• 현재 위치에서 선택할 수 있는 최소 점수를 계산하여 minDp 배열을 갱신한다.
  • minDp[0]은 minDp[0](왼쪽)과 minDp[1](중앙) 중 작은 값에 현재 값(arr[0])을 더한 값으로 업데이트된다.
  • minDp[2]은 minDp[2](오른쪽)과 minDp[1](중앙) 중 작은 값에 현재 값(arr[2])을 더한 값으로 업데이트된다.
  • minDp[1]은 minDp[0], minDp[1], minDp[2] 중 최소값에 현재 값(arr[1])을 더한다.

3.2 최대 점수 갱신

 

leftNum = maxDp[0]; midNum = maxDp[1]; rightNum = maxDp[2]; maxDp[0] = max(leftNum, midNum) + arr[0]; maxDp[2] = max(rightNum, midNum) + arr[2]; maxDp[1] = max(max(leftNum, midNum), rightNum) + arr[1];

• 최소값을 구하는 방식과 동일하지만, max 함수를 사용하여 최댓값을 갱신한다.

3.3 결과 출력

 

cout << *max_element(maxDp.begin(), maxDp.end()) << " " << *min_element(minDp.begin(), minDp.end());

• max_element()를 사용하여 maxDp에서 최댓값을 찾고 출력한다.
• min_element()를 사용하여 minDp에서 최솟값을 찾고 출력한다.

[소스 코드]

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;

vector<int> maxDp;
vector<int> minDp;
vector<int> arr;
int N;

void Input() {
	cin >> N;
	arr.resize(3);
	minDp.resize(3,999999);
	maxDp.resize(3,-1);
}
bool isInsideIdx(int idx) {
	if (idx >= 0 && idx < N)return true;
	return false;
}

void Game_Start() {
	for (int i = 0; i < 3; i++) {
		cin >> arr[i];
	}
	for (int i = 0; i < 3; i++) {
		minDp[i] = arr[i];
		maxDp[i] = arr[i];
	}
	
	for (int i = 1; i < N; i++) {
		cin >> arr[0] >> arr[1] >> arr[2];
		int leftNum = minDp[0];
		int midNum = minDp[1];
		int rightNum = minDp[2];

		minDp[0] = min(leftNum, midNum) + arr[0];
		minDp[2] = min(rightNum,  midNum) + arr[2];
		minDp[1] = min(min(leftNum, midNum), rightNum) + arr[1];

		leftNum = maxDp[0];
		midNum = maxDp[1];
		rightNum = maxDp[2];

		maxDp[0] = max(leftNum, midNum) + arr[0];
		maxDp[2] = max(rightNum, midNum) + arr[2];
		maxDp[1] = max(max(leftNum, midNum), rightNum) + arr[1];
	}

	cout << *max_element(maxDp.begin(), maxDp.end()) << " " <<
		*min_element(minDp.begin(), minDp.end());
	
}

int main(void) {
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	Input();
	Game_Start();
}