[C++] 백준 9465번: 스티커

🖍 문제

9465번: 스티커

9465번: 스티커

 

📄 풀이

이 문제를 바로 풀 수 있는 사람이 있을까?

풀 때마다 암기력으로 극복하는 중인데 이게 맞나 싶다.

💾 소스

#include <iostream>
#include <algorithm>

int main()
{
	int T; std::cin >> T;
	int sticker[2][100001];

	int dp[2][100001];
	dp[0][0] = 0;
	dp[1][0] = 0;

	while (T--)
	{
		int n; std::cin >> n;
		for (int i = 1; i <= n; i++)
			std::cin >> sticker[0][i];
		for (int i = 1; i <= n; i++)
			std::cin >> sticker[1][i];
        
		dp[0][1] = sticker[0][1];
		dp[1][1] = sticker[1][1];

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

		std::cout <<max(dp[0][n], dp[1][n])<< std::endl;

	}//T
}//main