BaekJoon 2096번: 내려가기(C++)

https://www.acmicpc.net/problem/2096

2096번: 내려가기

 

풀이법

1) 메모리의 제한이 4MB이므로 최소한의 배열을 이용하여 풀어야 하는 DP 문제이다.

max와 min 모두 2차원의 3x2배열을 만들어서 최대 값과 최솟 값을 구하였다.

2) 자세한 이해는 코드를 보며 공부하는 것이 더 효율적이리라 생각한다.

(1차원 배열로는 min max 값을 정확하게 구할 수 없으므로 나머지 연산자를 활용하여, 최대와 최솟값을 구해두었다.)

점화식을 잘못 세운 분들을 위한 Hidden Case 또한 source code 밑에 첨부하였다.

#include <string>
#include <vector>
#include <map>
#include <algorithm>
#include <iostream>
using namespace std;

int n;
int maxArr[3][2];
int minArr[3][2];
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
	cin >> n;
	int a, b, c;
	cin >> a >> b >> c;
	maxArr[0][0] = a;
	maxArr[1][0] = b;
	maxArr[2][0] = c;

	minArr[0][0] = a;
	minArr[1][0] = b;
	minArr[2][0] = c;
	for (int i = 1; i < n; i++)
	{
		int a, b, c;
		cin >> a >> b >> c;
		maxArr[0][i%2] = max(maxArr[0][(i+1)%2] + a, maxArr[1][(i + 1) % 2] + a);
		maxArr[1][i%2] = max(maxArr[0][(i + 1) % 2] + b, max(maxArr[1][(i + 1) % 2] + b, maxArr[2][(i + 1) % 2] + b));
		maxArr[2][i%2] = max(maxArr[1][(i + 1) % 2] + c, maxArr[2][(i + 1) % 2] + c);

		minArr[0][i % 2] = min(minArr[0][(i + 1) % 2] + a, minArr[1][(i + 1) % 2] + a);
		minArr[1][i % 2] = min(minArr[0][(i + 1) % 2] + b, min(minArr[1][(i + 1) % 2] + b, minArr[2][(i + 1) % 2] + b));
		minArr[2][i % 2] = min(minArr[1][(i + 1) % 2] + c, minArr[2][(i + 1) % 2] + c);


	}
	int maxRes = 0;
	int minRes = 1000000000;
	for (int i = 0; i < 3; i++)
	for (int i = 0; i < 3; i++)
	{
		if (maxRes < maxArr[i][(n+1)%2])
			maxRes = maxArr[i][(n+1)%2];
		if (minRes > minArr[i][(n+1)%2])
			minRes = minArr[i][(n+1)%2];
	}
	cout << maxRes << " " << minRes;

}

Hidden Case

3

1 0 0

0 1 0

0 0 1

Ans: 3 0

 

점화식을 잘못 세울 경우 Ans: 2 0의 값이 나오는 경우가 발생할 수 있다.

a, b, c 순서 대로 값이 들어올 경우를 생각했을 때, 접근할 수 있는 이전의 배열의 값 중 더 큰 것을 가져오는 것이 핵심이므로 이 부분을 찾아보고 고려한다면, 문제를 해결할 수 있을 것이다.