[백준] 2096 내려가기 (C++)

백준 2096 내려가기 문제
백준 2096 내려가기 소스코드

📄 문제 설명

Problem

N줄에 0 이상 9 이하의 숫자가 <세 개씩> 적혀 있다.
내려가기 게임은 첫 줄에서 시작해서 마지막 줄에서 끝나게 되는 놀이이다.

먼저 처음에 적혀 있는 세 개의 숫자 중에서 하나를 골라서 시작하게 된다.
그리고 다음 줄로 내려가는데, 다음 줄로 내려갈 때에는 다음과 같은 <제약 조건>이 있다.

ⓐ <바로 아래의 수>로 넘어가거나,
ⓑ 바로 <아래의 수와 붙어 있는 수>로만 이동할 수 있다.

이 제약 조건을 그림으로 나타내어 보면 다음과 같다.

별표는 현재 위치이고,
그 아랫 줄의 파란 동그라미는 다음 줄로 내려갈 수 있는 위치이며,
빨간 가위표는 내려갈 수 없는 위치가 된다.

숫자표가 주어져 있을 때, 얻을 수 있는 <최대 점수>와 <최소 점수>를 구하는 프로그램을 작성하시오.
점수는 위치했던 곳의 수의 합이다.

Input

첫째 줄 : N(1 ≤ N ≤ 100,000)이 주어진다.
다음 N개의 줄 : 숫자가 세 개씩 주어진다.
               숫자는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 중의 하나가 된다.

Output

첫째 줄에 얻을 수 있는 <최대 점수>와 <최소 점수>를 띄어서 출력한다.

Example Input

3
1 2 3
4 5 6
4 9 0

Example Output

18 6

📝 문제 해설

1번 줄부터 n번 줄까지 제약조건에 맞게 3개의 숫자중 골라서 따라 내려가며 합한 값의
<최댓값>과 <최솟값>을 구하는 문제이다.

이 문제를 자세히 보면 특징이 있는 것을 알 수 있다.

[i][0]자리에는 [i-1][0], [i-1][1]에서
[i][1]자리에는 [i-1][0], [i-1][1], [i-1][2]에서
[i][2]자리에는 [i-1][1], [i-1][2]에서 내려올 수 있는 것을 볼 수 있다.

최댓값을 구한다고 가정하고 점화식을 세우게 되면,

dp[i][0] = max(dp[i-1][0], dp[i-1][1]) + map[i][0];
dp[i][1] = max(dp[i-1][0], dp[i-1][1], dp[i-1][2]) + map[i][1];
dp[i][2] = max(dp[i-1][1], dp[i-1][2]) + map[i][2];

위와 같은 수식이 나오게 되고 for문을 돌아가며 최댓값과 최솟값을 구하면 된다.

⚠ 위 방식으로 해결 되지만 주의할 점이 있다.

dp의 크기를 [100010][3]으로 잡아주니 <메모리 초과>가 된다.

사실 <이전 값>과 <현재 값>을 저장해 놓을 곳만 있으면 문제를 풀 수 있다.
따라서, 현재 값을 저장할 최소한의 dp 배열을 만든 후
for문을 돌며 저장된 값을 tmp에 할당하고 점화식 연산을 통해 dp배열을 update하면 된다. 

</> Source Code

#include <bits/stdc++.h>
#define COL 3

using namespace std;

int small(int, int);
int big(int, int);
int small(int, int, int);
int big(int, int, int);

int main() {	
	int n, max, min;
	scanf("%d", &n);

	int dpMin[COL] = {0, };
	int dpMax[COL] = {0, };
	
	for(int i = 1; i <= n; i++){
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		
		int tmp0 = dpMax[0], tmp1 = dpMax[1], tmp2 = dpMax[2]; 	// 이전 값 저장
		dpMax[0] = big(tmp0, tmp1) + a;
		dpMax[1] = big(tmp0, tmp1, tmp2) + b;
		dpMax[2] = big(tmp1, tmp2) + c;
				
		tmp0 = dpMin[0], tmp1 = dpMin[1], tmp2 = dpMin[2];  // 이전 값 저장
		dpMin[0] = small(tmp0, tmp1) + a;
		dpMin[1] = small(tmp0, tmp1, tmp2) + b;
		dpMin[2] = small(tmp1, tmp2) + c;
	}
   
	max = big(dpMax[0], dpMax[1], dpMax[2]);	
	min = small(dpMin[0], dpMin[1], dpMin[2]);
	
	printf("%d %d", max, min);
	
	return 0;
}

int small(int a, int b){
	if(a < b){
		return a;
	}
	else{
		return b;
	}
}

int big(int a, int b){
	if(a > b){
		return a;
	}
	else{
		return b;
	}
}

int small(int a, int b, int c){
	if(a < b){
		return small(a, c);
	}
	else{
		return small(b, c);
	}
}

int big(int a, int b, int c){
	if(a > b){
		return big(a, c);
	}
	else{
		return big(b, c);
	}
}