🖍 문제
9465번: 스티커
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 두 줄에는 n개의 정수가 주어지며, 각 정수는 그 위치에 해당하는 스티커의
www.acmicpc.net
📄 풀이
이 문제를 바로 풀 수 있는 사람이 있을까?
풀 때마다 암기력으로 극복하는 중인데 이게 맞나 싶다.
💾 소스
#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