9465번: 스티커

Memo

• 현재 위치가 위에 있으면 (down[i]- 2) 값과 (down[i] - 1) 값 중 더 큰 값을 고르고, 아래에 있으면 (up[i] - 2) 값과 (up[i] - 1) 값 중 더 큰 값을 골라서 현재 위치와 합한 후 저장.
• 위와 같은 규칙을 n까지 적용시켜 n에 저장된 값들 중 최대값 출력

Code

제출 날짜

2021/03/10

메모리

5260 KB

시간

92 ms

#include <iostream>
#include <vector>
#include <algorithm>
#define endl "\\n"

typedef long long ll;
int T;
ll ans;
size_t n;
std::vector<ll> up;
std::vector<ll> down;

void input_faster()
{
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(0);
	std::cout.tie(0);
}

void input()
{
	input_faster();
	std::cin >> T;
}

void solve_input()
{
	std::cin >> n;
	up = std::vector<ll>(n + 1);
	down = std::vector<ll>(n + 1);
	for (size_t i = 1 ; i <= n ; i++)
		std::cin >> up[i];
	for (size_t i = 1 ; i <= n ; i++)
		std::cin >> down[i];
	ans = 0;
}

void solve()
{
	solve_input();
	for (size_t i = 2 ; i <= n ; i++)
	{
		up[i] = std::max(down[i - 1] + up[i] , down[i - 2] + up[i]);
		down[i] = std::max(up[i - 1] + down[i] , up[i - 2] + down[i]);
	}
	ans = std::max(up[n], down[n]);
}

void print_val()
{
	std::cout << ans << endl;
}

int main()
{
	input();
	while (T--)
	{
		solve();
		print_val();
	}
	return (0);
}