- DP 배열을 둬서, 각 자리마다 가능한 최댓값을 끝까지 구해 나간다.
- 2개의 행에서 각 자리의 최댓값은 -> (같은 행의 2칸 전, 다른 행의 2칸 전, 다른 행의 1칸 전) 중 최댓값에 자기 위치의 값을 더한 값이 된다.
- 앞에서부터 값을 구해나가기 때문에, DP 배열을 따로 둘 필요 없이 입력 받은 배열을 직접 수정해나가면서 구해도 된다.
#include <iostream>
using namespace std;
int t, n;
int r1[100001];
int r2[100001];
int main(void)
{
cin.tie(0);
ios_base::sync_with_stdio(0);
cin >> t;
for(int tc = 0 ; tc < t ; tc++)
{
int answer = 0;
cin >> n;
for(int i = 0 ; i < n ; i++)
cin >> r1[i]; // 값을 배열에 입력
for(int i = 0 ; i < n ; i++)
cin >> r2[i];
r1[1] += r2[0]; // 1번 열의 경우 먼저 따로 처리를 해줌
r2[1] += r1[0]; // 가능한 값이 대각선 위치밖에 없으므로, 해당 위치의 스티커값을 더해준다.
for(int i = 2, maxi, temp ; i < n ; i++) // 2번 열부터 반복 시작
{
temp = r1[i-2] > r2[i-2] ? r1[i-2] : r2[i-2]; // a b # -> # 의 자리에서 가능한 최댓값은, a c d 세 자리 중 최댓값을 더한 값
maxi = r2[i-1] > temp ? r2[i-1] : temp; // c d e
r1[i] += maxi;
if(r1[i] > answer) answer = r1[i];
temp = r2[i-2] > r1[i-2] ? r2[i-2] : r1[i-2]; // a b c -> # 의 자리에서 가능한 최댓값은, a b d 세 자리 중 최댓값을 더한 값
maxi = r1[i-1] > temp ? r1[i-1] : temp; // d e #
r2[i] += maxi;
if(r2[i] > answer) answer = r2[i];
}
cout << answer << '\n';
}
}
'PS > BOJ' 카테고리의 다른 글
[백준] 15663.cpp : N과 M (9) (0) | 2020.07.29 |
---|---|
[백준] 11725.cpp : 트리의 부모 찾기 (0) | 2020.07.28 |
[백준] 11053.cpp : 가장 긴 증가하는 부분 수열 (0) | 2020.07.26 |
[백준] 1016.cpp : 제곱 ㄴㄴ 수 (0) | 2020.07.26 |
[백준] 15657.cpp : N과 M (8) (0) | 2020.07.25 |