취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 5589번 문제인 おせんべい이다.
문제는 아래 링크를 확인하자.

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

각 행을 뒤집는 경우(최대 2^10 = 1024가지)마다 문제를 따로 생각해보자.

행을 뒤집는 경우를 고정했다면 각 열의 가능한 경우(2가지) 중 더 많은 1이 있게 하는 경우를 골라 더해 이 고정된 경우의 1의 개수의 최댓값을 구할 수 있다.

각 행마다 위의 값을 구해내 그중 최댓값을 답으로 출력하자.

같은 배치의 열의 경우 모두 같은 결과가 나오게 되므로 같은 열들을 압축해 문제를 빠르게 풀 수 있다.

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;

int arr[10][10000];
int cnt[512];

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

	int R, C; cin >> R >> C;
	int RR = (1 << R);
	int RRR = RR >> 1;
	for (int r = 0; r < R; r++) {
		for (int c = 0; c < C; c++) {
			cin >> arr[r][c];
		}
	}

	for (int c = 0; c < C; c++) {
		int tmp = 0;
		for (int r = 0; r < R; r++) {
			tmp *= 2;
			tmp += arr[r][c];
		}
		if (tmp >= RRR) tmp ^= RR - 1;
		cnt[tmp]++;
	}

	int ans = 0;
	
	for (int i = 0; i < RRR; i++) {
		int tmp = 0;
		for (int j = 0; j < RRR; j++) {
			int bits = 0;
			int ixorj = i ^ j;
			while (ixorj) {
				if (ixorj & 1) bits++;
				ixorj >>= 1;
			}
			tmp += max(R - bits, bits) * cnt[j];
		}
		ans = max(ans, tmp);
	}

	cout << ans;
}