백준 28422 - XOR 카드 게임 (C++)

문제

• 문제 링크

  
   BOJ 28422 - XOR 카드 게임 
  

• 문제 요약

$1.$ 한 번에 가져가는 카드들에 적혀있는 번호를 $XOR$ 연산한다.
$2.$ $1$에서 구한 값을 이진수로 변환했을 때, $1$의 개수만큼 점수를 획득한다.

$N$장의 카드 더미가 위에서부터 주어진다.
위 획득 기준으로 카드를 두 장 혹은 세 장씩 가져갈 때, 획득할 수 있는 최고 점수를 구해보자.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N ≤ 10^5$

$2^0 ≤ A_i ≤ 2^{10}$

알고리즘 분류

• 다이나믹 프로그래밍(dp)

풀이

간단한 $dp$ 문제이다.

$dp[i] :$ 지금까지 $i$장의 카드를 가져갔을 때, 이후 획득할 수 있는 최고 점수.

문제에서 제시하는 분기 방향 그대로,
임의의 $i$에서 $2$장의 카드를 가져갈 때 $/$ $3$장의 카드를 가져갈 때 중 최댓값을 취하면 된다.

$N$장의 카드를 정확히 가져가지 못하면 $0$점 처리되므로, 이를 유의하자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int n, a[100005], dp[100001];
 
int f(int p)
{
    if (p > n - 2) return p ^ n ? -1e9 : 0;
    int& t(dp[p]);
    if (!~t)
        t = max(f(p + 2) + __builtin_popcount(a[p + 1] ^ a[p + 2]), f(p + 3) + __builtin_popcount(a[p + 1] ^ a[p + 2] ^ a[p + 3]));
    return t;
}
int main()
{
    cin >> n;
    for (int i(1); i <= n; scanf("%d", &a[i++]));
    memset(dp, -1, sizeof dp);
    cout << max(0, f(0));
}

comment

끝