์•Œ๊ณ ๋ฆฌ์ฆ˜

  • ๋‚ด๋ ค์˜ฌ ์ˆ˜ ์žˆ๋Š” ๊ณณ์€ ๊ต‰์žฅํžˆ ํ•œ์ •๋˜์–ด์žˆ๊ณ , ์ˆœ์ฐจ์ ์œผ๋กœ ๊ฐ€์žฅ ์ž‘์€๊ฐ’์„ or ๊ฐ€์žฅ ํฐ๊ฐ’์„ ๊ตฌํ•˜๊ธฐ๋งŒ ํ•˜๋ฉด ๋˜๋Š” ๋ฌธ์ œ์ด๊ธฐ์— ์ผ์ฐจ์› DP๋กœ ํ•ด๊ฒฐ์ด ๊ฐ€๋Šฅํ•˜๋‹ค.
  • ์ด๋Ÿฐ ์ข…๋ฅ˜์˜ ๋ฌธ์ œ๋ฅผ โ€œ์Šฌ๋ผ์ด๋”ฉ ์œˆ๋„์šฐโ€ ๋ผ๊ณ  ๋ถ€๋ฅด๋Š” ๊ฒƒ ๊ฐ™๋‹ค

์ฝ”๋“œ

#include <iostream>
using namespace std;
 
int n, ansMax = -1, ansMin = 2000000000, cur[2][3], tCur[2][3];
 
int min(int a, int b) {
	return a < b ? a : b;
}
int max(int a, int b) {
	return a > b ? a : b;
}
 
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
 
	cin >> n;
 
	int a, b, c;
	cin >> cur[0][0] >> cur[0][1] >> cur[0][2];
	for (int i = 0; i < 3; i++)
		cur[1][i] = cur[0][i];
 
	for (int i = 1; i < n; i++) {
		cin >> a >> b >> c;
		memcpy(tCur, cur, sizeof(cur));
		cur[0][0] = max(tCur[0][0], tCur[0][1]) + a;
		cur[0][1] = max(max(tCur[0][0], tCur[0][1]), tCur[0][2]) + b;
		cur[0][2] = max(tCur[0][1], tCur[0][2]) + c;
		cur[1][0] = min(tCur[1][0], tCur[1][1]) + a;
		cur[1][1] = min(min(tCur[1][0], tCur[1][1]), tCur[1][2]) + b;
		cur[1][2] = min(tCur[1][1], tCur[1][2]) + c;
	}
 
	for (int i = 0; i < 3; i++) {
		ansMax = max(ansMax, cur[0][i]);
		ansMin = min(ansMin, cur[1][i]);
	}
 
	cout << ansMax << " " << ansMin;
}