https://www.acmicpc.net/problem/9465

이 문제는 dp로 접근했다.

개인적으로 dp 접근법을 열어준 문제가 포도주 시식, 계단 오르기

이렇게 있는 것 같은데 위 문제들과 같은 방식으로 접근했다.

먼저 i번째 위쪽, 아래쪽 스티커를 떼는 경우는 6가지로 나뉜다.

위쪽

1. i-1번째 아래쪽을 떼고 i번째 위쪽을 떼는 경우
2. i-1번째를 떼지 않고 i-2번째 위쪽을 떼는 경우
3. 2번과 같지만 i-2번째 아래쪽을 떼는 경우

아래쪽

1. i-1번째 위쪽을 떼고 i번째 아래쪽을 떼는 경우
2. i-1번째를 떼지 않고 i-2번째 위쪽을 떼는 경우
3. 2번과 같지만 i-2번째 아래쪽을 떼는 경우

이렇게 6가지의 점화 관계를 구현해주면 된다.

코드는 다음과 같다.

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

int t;
int n;

void solve(){
    int dp[100001][2];
    int arr[100001][2];
    cin >> n;
    int maxi;
    for(int i=0;i<n;i++) cin >> arr[i][0];
    for(int i=0;i<n;i++) cin >> arr[i][1];
    if(n!=1){
        for(int i=0;i<2;i++){dp[i][0]=arr[i][0];dp[i][1]=arr[i][1];}
        dp[1][0]+=dp[0][1]; dp[1][1]+=dp[0][0];
        maxi=max(dp[1][0],dp[1][1]);
    }
    else{
        for(int i=0;i<1;i++){dp[i][0]=arr[i][0];dp[i][1]=arr[i][1];}
        maxi=max(dp[0][0],dp[0][1]);
    }
    for(int i=2;i<n;i++){
        dp[i][0]=max(dp[i-1][1],max(dp[i-2][0],dp[i-2][1]))+arr[i][0];
        dp[i][1]=max(dp[i-1][0],max(dp[i-2][0],dp[i-2][1]))+arr[i][1];
        maxi=max(maxi,max(dp[i][0],dp[i][1]));
    }
    cout << maxi << '\n';
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> t;
    while(t--){
        solve();        
    }
    return 0;
}

test case가 있는 경우의 문제 : 특히 코드포스 의 경우 메모리를 리셋해주어야 하는데,

이때 위와 같이 새로운 함수를 하나 만들어 사용하자.