백준 14391 C++

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

이 문제는 비트마스킹으로 하는데 생각을 처음에 잘못해서 좀 오래 걸렸다.

예를 들어 아래 코드 상

1	1
0	0

이렇게 생긴게 3을 의미하는데 코드를 만들어 놓고 손으로 그림 그리며 생각할 때

0	0
1	1

이렇게 생각을 해서 하나하나 모두 출력해보다가 찾아냈다.

 

배열을 뒤집어서 가로를 확인한 것과 동일하게 t++로 할려고 했는데 배열을 뒤집은 대로 비트가 돌아가는 것이 아니기에 틀린 방법이었다.

 

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int n, m;
int result = 0;
int paper[5][5];
int visited[5][5];
vector<int> v;
vector<int> adds;

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

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		string temps; cin >> temps;
		for (int j = 0; j < temps.size(); j++) {
			paper[i][j] = temps[j] - '0';
			//temp[i][j] = s[j] - '0';
		}
	}

	//for (int i = 0; i < m; i++) {
	//	for (int j = 0; j < n; j++) {
	//		cout << paper[j][i];
	//	}
	//	cout << "\n";
	//}

	//int a = 3;
	//cout << (a & (1 << 0));
	
	for (int num = 0; num < (1 << n * m); num++) {		//0 = 세로, 1 = 가로로 친다. 모든 경우의 수를 체크하는 것이다.
		//cout << "\n\n num : " << num << "\n";
		int t = 0; int num2 = ~num;
		adds.clear();

		int add = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (num & (1 << t)) {		//num이 1<<t에 해당하는 비트가 켜져있다면
					add = add * 10 + paper[i][j];
				}
				else {
					//cout << "adding add : " << add << "\n";
					adds.push_back(add);
					add = 0;
				}
				t++ ;
			}

			if (add != 0) {
				//cout << "adding add : " << add << "\n";
				adds.push_back(add);
				add = 0;
			}
		}


		//cout << "sero\n" << "\n";
		add = 0;
		int gt = 0; int st = 0;
		for (int i = 0; i < m; i++) {
			gt = st;
			for (int j = 0; j < n; j++) {
				if (num2 & (1 << gt)) {		//num이 1<<t에 해당하는 비트가 켜져있다면
					add = add * 10 + paper[j][i];
				}
				else {
					//cout << "adding add : " << add << "\n";
					adds.push_back(add);
					add = 0;
				}
				gt += m;
			}

			st++;

			if (add != 0) {
				//cout << "adding add : " << add << "\n";
				adds.push_back(add);
				add = 0;
			}
		}

		int sum = 0;
		for (int i = 0; i < adds.size(); i++) {
			sum += adds[i];
		}

		//int asdf;
		//if (result < sum) {
		//	cout << "\n NEW Result : " << result << "\n";
		//	cin >> asdf;
		//}

		result = max(result, sum);
		
	}

	cout << result;
}