16. UVa-10264 The most potent Corner // XOR연산의 의미

-문제

<그림1: 문제 설명>

-문제 설명

문제 이해가 조금 힘들수도 있는데, 풀어서 설명해보면 다음과 같은 문제다.

차원 N이 주어지면 N개의 bit로 구성된 (b1,b2,...,bn)와 같은 n-dimensional bit좌표를 생각해볼 수 있다. 이 때 어떤 좌표 하나를 점으로 생각하면, 그 점과 하나의 bit만이 차이나는 다른 점을 이웃하는 점으로 정의한다. 또한, 이 점에 대해 weight가 주어지는데 이것은 입력에서 0,1,2,3,4,5,6...2ⁿ-1의 순서대로 주어진다. 즉 처음 주어지는 weight에 해당하는 점은(0,0,0,..,0,0) 다음은 (0,0,...,0,1), 다음은 (0,0,0,..,1,0) 그 다음은 (0,0,0,..,1,1)에 해당하는 weight가 주어지게 된다.

 

이 때 어떤 점의 potency를 이웃하는 점들의 weight를 모두 더한 것으로 정의한다. 이 때 이웃하는 두 점의 potency sum중 최대인 potency sum을 계산하는 문제다.

 

(pdf에서는 문제 설명을 대충 써놨다. 걍 큐브라고 써놓고 이웃하는 점이 뭔지는 common edge라는 용어를 써서 정의하는데 edge가 뭔지 안알랴줌)

 

코드는 그냥 주어지는 순서대로 input부분과 계산부분 출력부로 작성하면 되는데 아마 potency구할 때랑 potency sum 구할 때 이웃하는 점 구하는게 bit연산에 익숙하지 않다면 힘들 것이다. 이웃하는 점은 잘 생각해보면 한 bit만 차이나는 점이므로 문제에서 주어진 모든 2ⁿ개의 점에 대해 각 점마다 n개의 이웃하는 점이 있을 거라는걸 생각해볼 수 있다.(차이날 수 있는 bit가 n개 존재하므로)

 

따라서 하나의 점에 대해 bit하나가 차이나는 n개 점의 weight들을 모두 더해야 potency sum이 된다. 따라서 주어진 점 하나(Corner)의 bit 하나만을 뒤집은 새로운 corner를 만들어야 한다. 그 bit연산은 1과의 xor연산으로 수행할 수 있는데, xor연산의 다음과 같은 성질 때문이다. xor부호 앞의 bit를 우리가 control하는 bit, 뒤의 bit를 연산의 대상이 되는 bit로 생각해보자.

-XOR연산의 의미

1. 1 xor 0 = 1(뒤집힘)

2. 1 xor 1 = 0(뒤집힘)

3. 0 xor 0 = 0(그대로)

4. 0 xor 1 = 1(그대로)

 

즉, 어떤 bit를 0과 xor연산하면 그대로고 1과 xor연산하면 뒤집힌다. 따라서 하나의 bit만 1이고 나머지가 0으로 채워진 어떤 n-bit sequence를 하나의 corner에 대해 xor연산하게 되면 하나의 bit만이 뒤집혀서 이웃하는 corner가 나오게 된다. k의 위치만이 1인 bit는 (1<<k)로 생성할 수 있으므로 potency의 계산식은 주어진 2ⁿ개의 corner에 대해 다음과 같다. (1<<N은 2ⁿ이다.)

for (int corner = 0; corner < (1 << N); corner++) {
			potency = 0;
			//Potenct of the corner is the sum of weights of all neighbouring corners
			//the number of neighbouing corners is N
			for (int digit = 0; digit < N; digit++) {
				potency += weights[corner ^ (1 << digit)];
				//through xor, just change 1 bit of 'corner'
			}

따라서 전체 코드를 작성해보면 다음과 같다.

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int main() {
	int N, input,potency,max=0;
	while (cin>>N) {
		vector<int> weights;
		vector<int> potencies;
		max = 0;
		//1. input part. 1<<N means 2^n
		for (int i = 0; i < (1 << N); i++) {
			cin >> input;
			weights.push_back(input);
		}
		//2. compute each potencies
		for (int corner = 0; corner < (1 << N); corner++) {
			potency = 0;
			//Potenct of the corner is the sum of weights of all neighbouring corners
			//the number of neighbouing corners is N
			for (int digit = 0; digit < N; digit++) {
				potency += weights[corner ^ (1 << digit)];
				//through xor, just change 1 bit of 'corner'
			}
			potencies.push_back(potency);
		}
		//3. Find the maximum potencies sum
		//using same method, seeing all corner
		for (int corner = 0; corner < (1 << N); corner++) {
			for (int digit = 0; digit < N; digit++) {
				max=max<(potencies[corner] + potencies[corner ^ (1 << digit)])? (potencies[corner] + potencies[corner ^ (1 << digit)]):max;
			}
		}
		cout << max << endl;
	}
	return 0;
}