[백준][C++] 1322: X와 K

• 문제 링크: https://www.acmicpc.net/problem/1322

 

X+Y = X|Y를 만족하는 K번째로 작은 수를 구하는 것이 문제입니다.

일단 가장 먼저 생각해볼 수 있는건 루프로 X+Y == X|Y 체크를 해서 k번째 수를 직접 찾는건데요 당연히 시간 초과가 납니다. X, K <= 20억이기 때문에 이 방법은 어렵고요

X_(2) = 0000....00010101	// 21
Y_(2) = ????....????????

K = 3
K_(2) = 101

좀 더 생각을 해봅시다. X=21, K=3일 때 답을 먼저 말하자면 10(=1010_(2))입니다. 이건 적당히 손으로도 구할 수 있습니다

X_(2) = 0000....00010101	// 21
K_(2) = 11
---------------------------------
Y_(2) = 0000....10100000	// X ... (1)
Y_(2) = 0000....00000110	// X ... (2)
---------------------------------
Y_(2) = ????....???0?0?0
Y_(2) = 0000....00001010	// 10

K번째로 작은 Y를 구해야 되는데 어떻게 구할까요? (1)은 3번째로 작은 Y가 아니니 답이 아니고, (2)는 X+Y!=X|Y이므로 답이 아닙니다.

즉 X의 비트가 1인 부분은 Y에서는 0이어야합니다. 따라서 이 부분을 먼저 체크해주면 바꿀 수 있는 비트는 한정되어있습니다. 0으로 만든 비트를 제외하고 나머지 비트를 K의 비트와 동일하게 맞추면 정답인 Y를 계산할 수 있습니다

 

#include <iostream>
using namespace std;

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

	using ll = long long;
	
	ll x, k;
	cin >> x >> k;
	ll ans = 0LL;

	for (ll x_mask=1, ans_mask=1; k>0; x_mask*=2) {
		if (!(x & x_mask)) {
			if (k & ans_mask) {
				ans += x_mask;
				k -= ans_mask;
			}

			ans_mask *= 2;
		}
	}

	cout << ans;

	return 0;
}

비트마스킹으로 푼 코드입니다.

너무 오랜만에 문제를 푸니까 1<<n 이게 기억이 안나서 그냥 마스킹할때 두배씩 곱했습니다.