Boj 23257) 비트코인은 신이고 나는 무적이다

문제

백준 23257

설명

주어진 숫자의 범위의 한계로 xor 의 결과 값의 범위는 [0, 1023] 이 된다. 범위가 작기 때문에 dp 를 자연스럽게 떠올릴 수 있다.

m 개 선택 조건은 dp 를 할 때 최소 조합 갯수를 저장하면 처리할 수 있다.

중복 선택인 조건은 xor 의 특성을 이용해야한다. 같은 두 값에 대해 xor 연산을 하면 캔슬이 되고 xor 연산은 교환법칙이 성립한다. 그러므로 m 이 짝수이면 짝수개를 선택한 경우는 모두 가능하고 홀수인 경우도 마찬가지가 된다. 그런데 최소 조합 갯수만 저장하면 홀수 / 짝수 모두 가능한 경우를 할 수 없어진다. 그러므로 짝수/홀수 개의 조합을 모두 저장해야한다.

시간 복잡도

O(\(1024\mathrm{N}\))

코드

int arr[101];
int dp[2][1024]; // [짝/홀 개를 조합] 해서 [x] 가 가능한가

int main()
{
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		cin >> arr[i];
		arr[i] = abs(arr[i]);
	}

	fill(dp[0], dp[2], 1e9);
	dp[0][0] = 0;  // 0 개 선택 시 0 을 조합할 수 있음
	for (int i = 0; i < n; i++)
		for (int bOdd = 0; bOdd < 2; bOdd++)
			for (int j = 0; j < 1024; j++)
			{
				if (dp[!bOdd][j] == 1e9) continue;
				if (dp[!bOdd][j] == m) continue;

				int c = j ^ arr[i];
				dp[bOdd][c] = min(dp[bOdd][c], dp[!bOdd][j] + 1);
			}

	int ans = 0;
	for (int i = 0, j = m % 2; i < 1024; i++)
		ans = max(ans, dp[j][i] < 1e9 ? i : -1);

	cout << ans;
}