[백준] 29200 - 문제 수 줄이기 (c++)

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

 

문제 요약

N크기의 수열이 주어진다. 수열을 구간으로 분할하는데 인접한 수열끼리 크기가 같으면 안 된다. 수열끼리 xor한 값의 합이 최대가 되도록 분할하고 합을 출력해라.

 

풀이 (N)

• DP
• 애드혹

일단 xor은 각 비트 자리에 1이 단 하나만 있어야 비트가 켜지기 때문에 잘게 쪼갤 수록 이득이란 걸 알 수 있다. 언뜻 보고 1,2,3 크기로만 분할해서 최댓값을 만들 수 있을 줄 알았지만

6 1 1 2 4 8 8

이런 반례 케이스가 있었다(3까지 포함하면 22, 4까지 포함하면 24 나옴). 4까지 포함하니 최댓값을 만들 수 있었다.

 

제한시간이 넉넉해서 한 1~10까지 써도 상관은 없다. 제한적인 숫자로 최댓값을 구성할 수 있다는 걸 직감을 통해 알아내야 하는 애드혹 문제였다.

 

dp[i][j]를 i까지 나눴고 가장 마지막에 j크기로 나눴을 때 최댓값으로 정의하면 쉽게 답을 구할 수 있다.

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int n;cin >>n;
    int a[n+1];
    for(int i=1;i<=n;i++)
        cin>>a[i];
    
    vector<array<ll,5>> dp(n+1);
    for(int i=1;i<=n;i++) {
        dp[i].fill(-1e18);
        int x =a[i];
        for(int j=1;j<=min(i,4);j++) {
            for(int k=1;k<=4;k++)
                if(k!=j)
                    dp[i][j] =max(dp[i][j],dp[i-j][k]+x);
            x^=a[i-j];
        }   
    }

    cout <<*max_element(dp[n].begin(),dp[n].end());
}