9465: 스티커

• toc {:toc}

문제 확인하기

풀이

스티커 하나를 떼어 내면 왼쪽, 오른쪽, 위, 아래는 사용할 수 없다. 즉, 대각선에 있는 스티커를 가져올 수 있다. 아래와 같다.

또는, 아래와 같이 선택할 수 있다.

점프를 이해하기 위해 예시를 들면 다음과 같다.
맨 왼쪽 아래 30에서 시작한다고 했을 때 대각 두 번 10, 70을 얻는 것보다 3열 대각인 100을 얻는 것이 더 점수가 높을 수 있기 때문에 두 칸 뒤도 생각해줘야 한다. 세 칸 뒤인 4열의 경우로 바로 점프하는 경우는 앞의 2열, 3열 중 하나를 선택하는 것이 반드시 더 큰 값을 도출하기 때문에 해당하지 않는다.

만약, 50에서 시작한다고 했을 때 점프해서 3열의 100을 바로 더하는 것도 고려해줘야 할까? 해줄 필요 없다. 3열의 100을 더하는 경우에는 2열의 50을 더하는 것이 더 높은 값을 도출하기 때문에 대각의 경우만 고려해주면 된다.

#include <bits/stdc++.h>
using namespace std;
 
int n;
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    int t;
 
    cin >> t;
 
    while(t--){
        int stickers[2][100005] = {0,};
        int dp[2][100005] = {0,};
 
        cin >> n;
 
        for(int i = 0; i < 2; i++){
            for(int j = 0; j < n; j++){
                cin >> stickers[i][j];
            }
        }
        dp[0][0] = stickers[0][0];
        dp[1][0] = stickers[1][0];
 
        dp[0][1] = stickers[0][1] + dp[1][0];
        dp[1][1] = stickers[1][1] + dp[0][0];
 
        for(int i = 2; i < n; i++){
            dp[0][i] = max(dp[1][i-2], dp[1][i-1]) + stickers[0][i];
            dp[1][i] = max(dp[0][i-2], dp[0][i-1]) + stickers[1][i];
        }
 
        cout << max(dp[0][n-1], dp[1][n-1]) << '\n';
 
    }
 
    return 0;
}