[9465] 스티커

문제: https://www.acmicpc.net/problem/9465

9465번: 스티커

 

접근:

• 다음 스티커를 선택하는 경우는 두 가지이다: 1) +1 대각선을 선택하는 경우, 2) +2 대각선을 선택하는 경우가 있다.
• 이 두 경우 중 더 큰 값을 반환하는 경우를 선택한

• 주의할 점은 (0,0), (1,0)을 0으로 두어야 시작부터 +1 경우와 +2 경우 모두 본다는 점이다.

 

코드:

#include <iostream>
#include <memory.h>
#include <algorithm>

using namespace std;
int N;
int arr[2][100001];
int cache[2][100001];

// y,x를 선택했을 때의 최대 값을 반환한다 
int getMax(int y, int x)
{
	if (x > N) return 0;
	
	int& ret = cache[y][x];
	if (ret != -1) return ret;

	int cand1 = arr[y][x], cand2 = arr[y][x];
	if (!y)
	{
		cand1 += getMax(y + 1, x + 1);
		cand2 += getMax(y + 1, x + 2);
	}
	else
	{
		cand1 += getMax(y - 1, x + 1);
		cand2 += getMax(y - 1, x + 2);
	}

	return ret = max(cand1, cand2);
}

int main()
{
	ios::sync_with_stdio(false);
	int T;
	cin >> T;

	while (T--)
	{
		memset(cache, -1, sizeof(cache));

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

		cout << max(getMax(0, 0), getMax(1, 0)) << "\n";
	}			

	return 0;
}