[백준] 2096번 내려가기

2096번: 내려가기

최소 점수를 구하는 과정을 예로 들자면

 

현재의 첫 번째 칸의 최솟값은

그림에 나와있는 대로

min(이전의 첫 번째 칸의 최솟값 or 이전의 두 번째 칸의 최솟값)

+

현재의 첫 번째 칸의 숫자

이다.

 

현재의 두 번째 칸의 최솟값은

그림에 나와있는 대로

min(이전의 첫 번째 칸의 최솟값 or 이전의 두 번째 칸의 최솟값 or 이전의 세 번째 칸의 최솟값)

+

현재의 두 번째 칸의 숫자

이다.

 

현재의 세 번째 칸의 최솟값은

그림에 나와있는 대로

min(이전의 두 번째 칸의 최솟값 or 이전의 세 번째 칸의 최솟값)

+

현재의 세 번째 칸의 숫자

이다.

 

이런 식으로 N번째 줄까지 구한 뒤

이 세 개의 칸 중 가장 작은 값을 출력하면 된다.

 

최대 점수도 최소 점수와 같은 과정으로 최댓값을 구한 뒤

세 개의 칸 중 가장 큰 값을 출력하면 된다.

#include <iostream>
#include <algorithm>
using namespace std;
int N, a, b, c, tmp_a, tmp_b, tmp_c;
int Min[3], Max[3];
int main() {
	cin >> N >> a >> b >> c;
	Min[0] = Max[0] = a, Min[1] = Max[1] = b, Min[2] = Max[2] = c;
	for (int i = 1; i < N; i++) {
		cin >> a >> b >> c;
		tmp_a = min(Min[0], Min[1]), tmp_b = min(tmp_a, Min[2]), tmp_c = min(Min[1], Min[2]);
		Min[0] = a + tmp_a, Min[1] = b + tmp_b, Min[2] = c + tmp_c;
		tmp_a = max(Max[0], Max[1]), tmp_b = max(tmp_a, Max[2]), tmp_c = max(Max[1], Max[2]);
		Max[0] = a + tmp_a, Max[1] = b + tmp_b, Max[2] = c + tmp_c;
	}
	cout << max(max(Max[0], Max[1]), Max[2]) << " " << min(min(Min[0], Min[1]), Min[2]);
	return 0;
}