Bit Masking & Prefix Sum (BOJ 15661, BOJ 21758)

랩실에서 과제 하려다가 초급 스터디를 들었는데 많은 걸 배웠고 재밌었다.

끝나고 스터디에서 다룬 문제들 풀다가 기록하고 싶은 것들

 

* Bit Masking *

BOJ 15661 링크와 스타트

 

한 팀을 기준으로 그 팀에 속해 있는 사람들을 비트로 관리할 때

두 사람 (i, j)이 같은 팀에 속해 있는지는 둘 다 비트가 켜져 있거나 꺼져 있는지로 확인할 수 있다.

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;

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

	int ans = INT_MAX;
	for (ll state = 1; state < (1 << n) - 1; ++state) {
		int sum = 0;
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				bool is_i = state & (1 << i);
				bool is_j = state & (1 << j);
				if (is_i == is_j) {
					sum += (arr[i][j] + arr[j][i]) * (is_i ? 1 : -1);
				}
			}
		}

		ans = min(ans, abs(sum));
	}
	
	cout << ans << kEndl;

	return 0;
}

 

스터디에서

두 팀의 능력치 ‘차이’만 구하면 되므로

비트가 둘 다 켜져 있을 때는 변수에 (Sij + Sji) 값을 더하고, 둘 다 꺼져 있을 때는 뺀다,

그리고 그 최종 결과의 절댓값을 구한다!

 

라는 설명을 듣고

‘처음에 arr 값을 다 더해서 total_sum을 구해두고

맨 마지막에 abs(sum - (total_sum - sum))을 구해도 될 듯?

싶었는데 안 되더라

 

다시 한번,

비트가 둘 다 켜져 있거나 둘 다 꺼져 있을 때만 (Sij + Sji) 값을 더하기 때문에

무작정 total_sum을 구하는 건 틀렸다.

 

잠시 뇌를 빼고 있었던 거 같다.

* Prefix Sum *

BOJ 21758 꿀 따기

처음 봤을 땐

되게 경우의 수가 많은 거 같은데 이걸 어떻게 처리하지?

싶었는데 설명을 듣고 보니 경우의 수는

꿀 - 벌 - 벌

벌 - 꿀 - 벌

벌 - 벌 - 꿀

이렇게 세 가지로만 나뉜다. 신기했다.

 

그리고 각각에 대해서 최선의 상황을 찾으면 되는데,

벌 - 꿀 - 벌 상황에서는 벌들이 꿀 쪽으로 다가오기 때문에 꿀이 있는 칸만 두 번 세게 되고,

꿀 - 벌 - 벌, 벌 - 벌 - 꿀 상황에서는 가장자리에 있는 벌과 꿀이 무조건 제일 마지막 칸에 있는 게 좋고, 가운데 벌의 위치만 정하면 된다.

 

그래서 이것도, 다 해보면 된다!

O(n)으로 해당 칸에 벌이 위치할 때의 합을 구해서 이 중에서 최댓값을 구하면 된다.

이때 가운데 벌이 위치하는 칸은 꿀을 못 따므로 이것도 빼줘야 하는 거 잊지 말기

 

그리고 여기서 ‘구간의 합’이 필요하므로 prefix sum를 사용하는 거다.

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n; cin >> n;

	vector<ll> arr(n + 1); // 1-based
	vector<ll> pre_sum(n + 1); // 1-based
	for (int i = 1; i <= n; ++i) {
		cin >> arr[i];
		pre_sum[i] = arr[i] + pre_sum[i - 1];
	}

	ll ans = 0;

	// bee - honey - bee
	ll max_honey = 0;
	for (int i = 2; i <= n - 1; ++i) {
		max_honey = max(max_honey, arr[i]);
	}
	ans = max(ans, pre_sum[n - 1] - pre_sum[1] + max_honey);

	// honey - bee - bee
	// honey should be at index 1, second bee should be at index n
	// looking for the first bee's location
	for (int i = 2; i <= n - 1; ++i) {
		// ans = max(ans, 2 * (pre_sum[i - 1] - pre_sum[0]) + pre_sum[n - 1] - pre_sum[i]);
		ans = max(ans, pre_sum[i - 1] + (pre_sum[n - 1] - arr[i]));
	}

	// bee - bee - honey
	for (int i = 2; i <= n - 1; ++i) {
		// ans = max(ans, 2 * (pre_sum[n] - pre_sum[i]) + pre_sum[i - 1] - pre_sum[1]);
		ans = max(ans, (pre_sum[n] - pre_sum[1] - arr[i]) + pre_sum[n] - pre_sum[i]);
	}

	cout << ans << kEndl;

	return 0;
}

Bit masking과 prefix sum 모두 그 자체가 독립적으로 어떠한 문제의 풀이라기보다는

이런 식으로 필요한 상황에 사용하는 경우가 많다는 말이 인상적이었다.

 

그리고 여담으로

오늘 간단한 prefix sum 문제에서는 그냥

cin >> arr[i];

arr[i] += arr[i - 1];

했었는데 절대 그러지 말아야겠다.

 

좀 메모리 낭비인 거 같아서 뭔가 자꾸 변수를 더 안 쓰는 습관이 있는데

각자 이름에 맞게 본인의 역할이 있는 거니까.

낭비가 아니라 투자라고 생각해야겠다.

 

 

 

 

 

 

https://blog.naver.com/mini_gb/223072932413

Bit Masking & Prefix Sum (BOJ 15661, BOJ 21758)