[백준/C++] 도미노 예측 (No. 17943)

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제는 xor 연산에 대해 잘 알고 있으면 쉽게 풀 수 있는 문제다.

 

xor 연산은 2진법으로 표현한 뒤 두 수를 비교했을 때 같은 자리에 있는 수가 같으면 0 다르면 1로 표현하는 연산이다.

 

즉, A (xor) A는 같은 수 이므로 모든 자리에 있는 수가 같으므로 값이 0이 된다.

또한 A (xor) 0을 연산할 경우 0과 연산했으므로 0은 모든 자리에 있는 수가 0이므로 결과 값이 0이 된다.

 

이를 이용하면 누적해서 xor을 계산해 둠으로써 쿼리의 연산을 빠르게 해결할 수 있다.

 

아래 그림을 보며 생각해보자

fig1

 

위 그림에 따르면, A와 B를 xor 연산한 a와 B와 C를 연산한 b를 xor 연산하면 A와 C를 xor 연산한 값을 알 수 있다.

 

마찬가지로 a(xor)b(xor)c 는 A(xor)B (xor) B(xor)C (xor) C(xor)D = A (xor) D 임을 알 수 있다.

 

이렇게 누적해서 xor연산을 이어나가면 첫번째 수인 A와 i번째 수를 xor 연산한 값을 전부 알 수 있게 된다.

 

이후 누적한 값들을 이용하면 x번째 수와 y번째 수를 xor 연산한 값도 쉽게 알 수 있다.

A(xor)x (xor) A(xor)y = x (xor) y로 찾을 수 있기 때문이다.

 

두 번째 쿼리도 마찬가지다 x번째 수의 값이 d일 때, y번째 수의 값을 구하려는 것이므로 첫 번째 쿼리의 x(xor)y 를 계산하는 방법을 이용하면 된다.

 

x(xor)y 값을 알고 있으며, 그 값을 v라고 가정해보자.

 

그러면 x(xor)v를 계산하면 x(xor) x(xor)y 에서 x(xor)x는 0이므로 결과값이 y가 된다.

 

이렇게 xor 연산을 누적 계산해 첫번째 수 A와 xor한 값을 미리 저장해 둔다면 쉽게 쿼리의 답을 알 수 있다.

 

 

[아이디어 정리]

1. xor 연산의 특징을 이용해 첫 번째 수와 i번째 수를 xor 연산한 값들을 저장하는 배열을 만든다.
2. 위에서 미리 계산한 값을 이용해 쿼리에 따라 경우를 구분하고 값을 빠르게 계산한다.

 

 

Code

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	int N,Q;
	cin >> N>>Q;
	// input=> i번과 i+1의 xor
	vector<int> nuX(N, 0); // 1번과 i+1번 수의 xor값
	int xx;
	for (int i=1; i<N; i++)
	{
		cin >> xx;
		nuX[i] = nuX[i-1]^xx;
	}
	int a, b, c, d;
	for (int i=0; i<Q; i++)
	{
		cin >> a;
		if (a==0)
		{
			cin >> b >> c;
			cout << (nuX[c-1]^nuX[b-1]) << "\n";
		}
		else
		{
			cin >> b >> c >> d;
			cout << (nuX[b - 1] ^ nuX[c - 1]^d) << "\n";
		}
	}
	return 0;
}

---

 

사실 처음에 누적해서 계산한 xor 연산한 값을 잘못 사용할 뻔 했다

다행히 빠르게 눈치채 쿼리에 들어가는 연산을 수정해 쉽게 풀 수 있었다

xor 연산을 잘 모르면 어렵게 느껴질 수 있는 문제였던 것 같다

fig2

 

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