문제

  • 2행 n열로 배치되어있는 2n개의 스티커를 떼어낸다. 떼어낼 수 있는 스티커 점수의 최대값을 구하라

입력

  • 첫째 줄에 테스트 케이스 T가 주어지며 각 테스트 케이스의 첫 번째 줄에는 n 그 다음에는 n개의 배열이 2번 주어진다.

출력

예제 입력
2
5
50 10 100 20 40
30 50 70 10 60
7
10 30 10 50 100 20 40
20 40 30 50 60 20 80
예제 출력
260
290

접근

  • 다이나믹 프로그래밍을 어떻게 사용할까?

내가 생각한 풀이

  • 각 스티커에 접근 할 수 있는 칸은 어디어디인가?
  • 한 칸 떨어진 대각선에 위치한 스티커와 2칸 떨어진 스티커 2장이 원하는 스티커에 접근 할 수 있는 스티커들이다!
    • 저 위치에 있는 스티커들의 누적값 + 현재 스티커의 값 중에 최대값을 찾아서 dp 배열에 저장해주면 된다.
  • index로 따지면 [i][0]에는 [i-1][1], [i-2][0], [i-2][1]이 접근 할 수 있다.

코드

#include<iostream>
using namespace std;
int main(void){
  int iter;
  cin>>iter;
  for(int i = 0 ;i<iter;i++){
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
    int c, m = -1, n[100002][2], dp[100002][2] ={0, };
    cin>>c;
    for(int j = 1 ;j<=c;j++){
      cin>>n[j][0];
    }
    for(int j = 1 ;j<=c;j++){
      cin>>n[j][1];
    }
    dp[1][0] = n[1][0]; dp[1][1] = n[1][1];
    for(int j = 2 ;j<=c;j++){
      dp[j][0] = max(dp[j-1][1],max(dp[j-2][0],dp[j-2][1]))+n[j][0];
      dp[j][1] = max(dp[j-1][0],max(dp[j-2][0],dp[j-2][1]))+n[j][1];
    }
    cout<<max(dp[c][0],dp[c][1])<<endl;
  }
  return 0;
}