[Baekjoon,9465] 스티커

먼저 방향을 정해야 한다. 방향은 왼쪽에서 오른쪽으로 진행하자. 만약 진행 중 현재 스티커를 선택한다면 오른쪽과 아래쪽에 붙어있는 스티커는 이용할 수 없다. 그러면 다음 스티커는 대각선 방향 스티커이다. 그런데 이 스티커 대신 이 보다 한 칸 오른쪽에 있는 스티커를 선택하는 것이 더 결과가 커질 수 있다. 예를 들어 아래와 같은 경우를 보자.

. X . 30 100 10
X . X 10  60 10

현재 X표시를 한 부분이 선택한 부분이라고 가정하자. 이때 30을 선택하는 것 보다 30에 해당하는 열을 선택하지 않고 100을 선택하는 결과 값이 더 크다. 이처럼 두 가지 경우를 나눠서 현재 위치의 최대값을 메모이제이션 하면 해결할 수 있다.

구현

이를 코드로 구현하면 아래와 같다. 다음 선택지의 경우 !연산자를 이용하여 간단히 접근하고 있다.

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

const int MAX_N = 100001;

int N;
int score[2][MAX_N], cache[2][MAX_N];

int getMaxScore(int r, int c)
{
	if (c >= N)
		return 0;
	
	int& ret = cache[r][c];
	if (ret != -1)
		return ret;

	return ret = score[r][c] + max(getMaxScore(!r, c + 1), getMaxScore(!r, c + 2));
}

int main()
{
	int T;
	cin >> T;
	while (T--)
	{
		cin >> N;
		for (int r = 0;r < 2;++r)
			for (int i = 0;i < N;++i)
				scanf("%d", &score[r][i]);
		
		int ret = 0;
		memset(cache, -1, sizeof(cache));
		ret = max(getMaxScore(0, 0), getMaxScore(1, 0));
		
		cout << ret << endl;
	}
}