[C++] 백준 15645번: 내려가기 2

문제 링크

15645번: 내려가기 2

문제 요약

N개의 줄이 있고, 각 줄에는 3칸이 있다. 각 칸에는 숫자가 있다. 아래 줄로 내려갈 때, 바로 아래와 인접한 칸으로 이동할 수 있다. 이때, 이동하면서 거쳐가는 칸에 적힌 수의 합의 최댓값과 최솟값을 구해야 한다.

접근 방법

쉬운 DP 문제입니다. 첫번째 줄은 그 줄에 적힌 값을 dp라는 배열에 저장합니다. 두번째 줄부터는, 바로 위의 인접한 칸의 dp 배열의 값과, 현재 칸에 적힌 값의 합을 dp 배열에 저장합니다.

내려가기를 풀 때, 이렇게 제출했다가 MLE를 받았었는데, 이 문제에서 코드를 재활용 해봤습니다.

코드

#include <bits/stdc++.h>

using namespace std;

int arr[100001][3], dp[100001][3];

int main(void)
{
	int n, res1, res2;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i][0] >> arr[i][1] >> arr[i][2];

	dp[1][0] = arr[1][0];
	dp[1][1] = arr[1][1];
	dp[1][2] = arr[1][2];

	for (int i = 2; i <= n; i++)
	{
		dp[i][0] = max(dp[i - 1][0], dp[i - 1][1]) + arr[i][0];
		dp[i][1] = max(dp[i - 1][0], max(dp[i - 1][1], dp[i - 1][2])) + arr[i][1];
		dp[i][2] = max(dp[i - 1][1], dp[i - 1][2]) + arr[i][2];
	}

	res1 = max(dp[n][0], max(dp[n][1], dp[n][2]));

	dp[1][0] = arr[1][0];
	dp[1][1] = arr[1][1];
	dp[1][2] = arr[1][2];

	for (int i = 2; i <= n; i++)
	{
		dp[i][0] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][0];
		dp[i][1] = min(dp[i - 1][0], min(dp[i - 1][1], dp[i - 1][2])) + arr[i][1];
		dp[i][2] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][2];
	}

	res2 = min(dp[n][0], min(dp[n][1], dp[n][2]));

	cout << res1 << ' ' << res2;
	return 0;
}