내려가기 (feat. 백준, 2096번)

내려가기
https://www.acmicpc.net/problem/2096

2096번: 내려가기

반응형

// woohyeon.kim
// https://www.acmicpc.net/problem/2096
#include <iostream>
#include <algorithm>
using namespace std;
char arr[100000][3];
int dp[100000][3];
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register int N;
	cin >> N;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < 3; ++j)
			cin >> arr[i][j], arr[i][j] -= '0', dp[i][j] = 0;
	for (register int i = 0; i < 3; ++i)
		dp[0][i] = arr[0][i];
	// max 구하기
	for (register int i = 0, j, t; i < N - 1; ++i)
		for (j = 0; j < 3; ++j)
			for (t = j - 1; t <= j + 1; ++t)
				if (0 <= t && t < 3)
					dp[i + 1][t] = max(dp[i + 1][t], dp[i][j] + arr[i + 1][t]);
	cout << *max_element(&dp[N - 1][0], &dp[N - 1][3]) << " ";
	// min 구하기
	for (register int i = 0, j, t; i < N - 1; ++i)
		for (j = 0; j < 3; ++j)
			for (t = j - 1; t <= j + 1; ++t)
				if (0 <= t && t < 3)
					dp[i + 1][t] = min(dp[i + 1][t], dp[i][j] + arr[i + 1][t]);
	cout << *min_element(&dp[N - 1][0], &dp[N - 1][3]) << "\n";
	return 0;
}
// *&)*@*

1. 두번째줄은 첫번째줄의 어디에서 시작되는가 만 본다면 세번째줄 또한 동일한 루틴입니다.
2. 첫번째줄을 t 라고 한다면 t - 1 ~ t + 1 까지가 연산의 범위입니다.
3. 첫번째줄의 1번에서 시작된다면 두번째 줄은 첫번째줄의 1번 + 1번 또는 첫번째줄의 1번 + 2번 이 됩니다.
4. 더한 결과에 대해서 max 또는 min을 누적시켜나가고 또한 위의 과정을 N까지 반복한다면 결과가 나옵니다.