❓문제 소개

문제 : 백준 2096 내려가기

난이도 : 골드 5

문제 요약
1. N줄에 0이상 9이하의 숫자가 세 개씩 적혀 있습니다.
2. 첫 줄에 주어지는 세 개의 숫자 중에서 하나를 골라서 내려가기를 시작합니다.
3. 내려갈때는 바로 아래의 수로 넘어가거나, 바로 아래의 수와 붙어 있는 수로만 이동할 수 있습니다.
4. 내려가면서 해당 위치의 점수 합을 구해 최대합과 최소합을 구합니다.

• 별표는 현재 위치
• O 는 내려갈 수 있는 위치
• X 는 내려갈 수 없는 위치

• N의 범위는 1이상 10만 이하 입니다.
• 얻을 수 있는 최대 점수와 최소 점수를 출력합니다.

✏️ 문제 해결 방법

이 문제는 메모리 초과가 나지않도록 해야하는 문제였습니다.

N의 범위인 1이상 10만 이하를 고려해서 배열을 arr[10만][3칸] 으로 받는 배열, 최대를 구하는 배열, 최소를 구하는 배열을 선언하고 문제를 풀게되면 메모리 초과가 발생할 수 밖에 없는 것이죠.

이 문제는 arr[2][3] 배열로 해결이 가능합니다.

내려가면서 지금까지의 합을 계속 저장해두지 않고 한 줄 전까지의 합 중에서 최대 혹은 최소를 저장해둡니다.

int a[100004][4]; //내려가기 정보 받기
int mx[2][4]; //최대합
int mn[2][4]; //최소합

최소와 최대를 구하는 방법을 비슷하므로 지금 부터는 최대합 기준으로만 설명하겠습니다.

mx[1][i] : 이전까지의 최대합을 비교해서 최대합을 알아냅니다.
mx[0][i] : mx[1][i]가 알아온 최대합을 이후 연산에서 사용하기 위해서 저장합니다.

//초기화
for(int i=1; i<=n; i++){
	for(int j=1; j<=3; j++){
		cin >> a[i][j];
		if(i == 1){
			mx[0][j] = a[i][j]; //첫줄까지 최대합 
			mn[0][j] = a[i][j]; //첫줄까지 최대합 
		}
	}
}

//첫 번째 칸으로 가기 위해서는 첫 번째 칸과 두 번째 칸에서 이동가능
mx[1][1] = a[i][1] + max(mx[0][1], mx[0][2]);

//두 번째 칸으로 가기 위해서는 첫 번째 칸, 두 번째 칸과 세 번째 칸에서 이동가능
mx[1][2] = a[i][2] + max({mx[0][1], mx[0][2], mx[0][3]});

//세 번째 칸으로 가기 위해서는 두 번째 칸과 세 번째 칸에서 이동가능
mx[1][3] = a[i][3] + max(mx[0][2], mx[0][3]);

mx[0][1] = mx[1][1]; //다음 연산을 위해 지금까지의 최대합을 mx[0][i]에 저장합니다.
mx[0][2] = mx[1][2];
mx[0][3] = mx[1][3];

💻 전체코드

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int n;
int a[100004][4];
int mx[2][4];
int mn[2][4];
int main(void){
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> n;
	for(int i=1; i<=n; i++){
		for(int j=1; j<=3; j++){
			cin >> a[i][j];
			if(i == 1){
				mx[0][j] = a[i][j]; //첫줄까지 최댓값 
				mn[0][j] = a[i][j]; //첫줄까지 최솟값 
			}
		}
	}
	
	for(int i=2; i<=n; i++){
		mx[1][1] = a[i][1] + max(mx[0][1], mx[0][2]);
		mx[1][2] = a[i][2] + max({mx[0][1], mx[0][2], mx[0][3]});
		mx[1][3] = a[i][3] + max(mx[0][2], mx[0][3]);
		
		mx[0][1] = mx[1][1];
		mx[0][2] = mx[1][2];
		mx[0][3] = mx[1][3];
		
		mn[1][1] = a[i][1] + min(mn[0][1], mn[0][2]);
		mn[1][2] = a[i][2] + min({mn[0][1], mn[0][2], mn[0][3]});
		mn[1][3] = a[i][3] + min(mn[0][2], mn[0][3]);
		
		mn[0][1] = mn[1][1];
		mn[0][2] = mn[1][2];
		mn[0][3] = mn[1][3];
	} 
	
	cout << max({mx[0][1], mx[0][2], mx[0][3]}) << ' ' << min({mn[0][1], mn[0][2], mn[0][3]});
	return 0;
}

메모리 초과를 해결하는 방법을 떠올리는게 어려웠네요..