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

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

문제

---

XOR 카드 게임이란 N장의 카드 더미가 있을 때, 맨 위에서부터 카드를 두 장 혹은 세 장씩 가져가 점수를 획득하는 게임이다. 이 게임에서 점수는 아래 단계를 거쳐 누적해서 획득할 수 있다.

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

게임을 진행하며 주의할 점은 마지막에 카드 한 장이 남는 상황이 존재할 수 있는데, 이 경우엔 모든 점수를 잃고 0점으로 게임을 종료하게 된다. 이 게임에서 얻을 수 있는 최고 점수를 계산하시오.

 

입력

---

첫째 줄에 카드 더미에 있는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 100000)

둘째 줄에 각 카드에 적힌 정수 A1,A2,⋯,AN이 공백으로 구분되어 주어진다. (20 ≤ Ai < 210; Ai는 카드 더미의 위에서부터 i번째 카드에 적힌 수이다.)

 

출력

---

이 게임에서 획득할 수 있는 최고 점수를 출력한다.

 

문제 풀이

---

dp 문제.

 

맨 위에서부터 카드를 가져가므로 이전에 저장된 값을 사용하는 dp를 활용하면 된다. 처음 존재하는 카드의 개수가 1개라면 가져갈 수 있는 카드가 없고 한 장만 남게 되므로 0점이다. 2개가 존재한다면 2개를 선택하고, 3개가 존재한다면 3개를 선택하고, 그보다 더 많은 수의 카드가 있다면 2개 / 3개 선택을 통해 무조건 모든 카드를 비울 수 있다. 따라서 이 경우에 카드가 한 장 남아 0이 되는 경우는 없다.

점수를 저장하는 배열이 dp라고 하고, dp[i]는 해당 인덱스를 마지막으로 하여 카드를 가져갔을 때의 점수의 총 합이라고 하자. 2장을 가져갔다면 dp[i] = dp[i-2] + 이번 턴 점수이고, 3장을 가져갔다면 dp[i] = dp[i-3] + 이번 턴 점수이다. 이번 턴 점수는 문제에 따라 2장인 경우, arr[i-1] ^ arr[i]이고 3장인 경우 arr[i-2] ^ arr[i-1] ^ arr[i]이다. 이 두가지 값을 비교하여 큰 값을 저장하고, 맨 마지막 인덱스의 값을 출력해주면 된다.

4번째에 위치한 카드의 경우 1장 + 3장으로 가져가지 못하므로 2장 + 2장인 경우만 저장해야 한다.

 

아래는 코드.

#include <iostream>
using namespace std;

int countBit(long long temp)
{
	if (temp == 0)
	{
		return 0;
	}
	return temp % 2 + countBit(temp / 2);
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	cin >> N;
	int* arr = new int[N];
	int* dp = new int[N];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	if (N == 1)
	{
		cout << 0 << "\n";
	}
	else
	{
		int num = arr[0] ^ arr[1];
		dp[1] = countBit(num);
		if (N >= 3)
		{
			dp[2] = countBit(arr[0] ^ arr[1] ^ arr[2]);
		}
		for (int i = 3; i < N; i++)
		{
			int second = arr[i - 1] ^ arr[i];
			int third = arr[i - 2] ^ arr[i - 1] ^ arr[i];
			dp[i] = dp[i - 2] + countBit(second);
			if (i != 3)
			{
				dp[i] = max(dp[i], dp[i - 3] + countBit(third));
			}
		}
		cout << dp[N - 1] << "\n";
	}
	return 0;
}