[백준/C++] 9495번_스티커

문제는 다음과 같습니다.

두 개의 배열이 있는데,
먼저 배열 a에는 입력받는 배열을 넣었습니다.
a[i][j]는 그대로 i행, j열에 있는 항을 의미합니다.

그리고 문제를 풀기 위한 핵심인 dp배열은 다음과 같습니다.

dp[N][i] : N번째 열에서의 경우

그리고 N번째 열에서 dp[N][i]는 i=0, 1, 2 총 세 가지 경우의 수를 갖습니다.

• dp[N][0]: 스티커를 아무것도 선택하지 않았을 경우
• dp[N][1]: a[0][N]번째 스티커를 선택했을 경우
• dp[N][2]: a[1][N]번째 스티커를 선택했을 경우

그리고 각각의 경우에 대해서 구하면 다음과 같습니다.

• dp[N][0] = max(dp[N-1][0], dp[N-1][1], dp[N-1][2])
• dp[N][1] = a[0][N] + max(dp[N-1][0], dp[N-1][2])
• dp[N][2] = a[1][N] + max(dp[N-1][0], dp[N-1][1])

그리고 구하는 최종 답은
행 N의 세 가지 경우 중 가장 큰 값을 구하면 됩니다.

전체 코드는 다음과 같습니다.

#include <bits/stdc++.h>
using namespace std;

int a[2][100001]={0, };

void func(int l){
  long long dp[100001][3]={0, };
  dp[0][0]=0; dp[0][1]=a[0][0]; dp[0][2]=a[1][0];

  for(int i=1; i<l; i++){
    dp[i][0] = max(dp[i-1][0],dp[i-1][1]);
    dp[i][0] = max(dp[i][0], dp[i-1][2]);
    dp[i][1] = (a[0][i]) + max(dp[i-1][0],dp[i-1][2]);
    dp[i][2] = (a[1][i]) + max(dp[i-1][0],dp[i-1][1]);
  }

  long long max_el = max(dp[l-1][0], dp[l-1][1]);
  max_el = max(max_el, dp[l-1][2]);
  cout<<max_el<<"\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, tmp; cin>>n;
    for(int i=0; i<n; i++){
      cin>>tmp; int len=tmp;
      for(int j=0; j<2; j++){
        for(int k=0; k<len; k++){
          cin>>tmp; a[j][k]=tmp;
        }
      }
      func(len);
    }
    return 0;
}