백준 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;
}

 

같은 문제를 다시 풀어봤는데 이 방식이 더 이해하기가 편할 것 같다.

굳이 돌리지 않고 나아가는 방향을 설정해서 나아간다.

#include <bits/stdc++.h>

using namespace std;

//0은 세로, 1은 가로로 계산하자

int n, m; int tempNum;
vector<vector<int>> nums(5);
int bits[5][5];
int visited[5][5];
int maxResult = 0;

void findBit(int y, int x, int bit) {
	visited[y][x] = 1;
	//cout << "y : " << y << " x : " << x << "\n";

	if (bit == 1) {
		tempNum += nums[y][x];
		if (x + 1 >= m) {		// 범위, 방문, bit가 다르다면
			return;
		}
		if ((visited[y][x + 1] && (bits[y][x + 1] != bit))) {
			return;
		}

		tempNum *= 10;
		findBit(y, x + 1, bit);

	}
	else {
		tempNum += nums[y][x];
		if (y + 1 >= n) {
			return;
		}
		if ((visited[y + 1][x] && (bits[y + 1][x] != bit))) {
			return;
		}

		tempNum *= 10;
		findBit(y + 1, x, bit);
	}
}



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

	cin >> n >> m;

	char c;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c; 
			int num = c - '0';

			nums[i].push_back(num);
		}
	}

	for (int t = 0; t < (1 << n * m); t ++) {		//모든 경우의 수를 계산한다.
		//cout << "t : " << t << "\n";
		fill(&visited[0][0], &visited[0][0] + 5 * 5, 0);
		fill(&bits[0][0], &bits[0][0] + 5 * 5, 0);

		for (int i = 0; i < n; i++) {						//비교하기 쉽도록 bits라는 array에 넣어둔다.
			for (int j = 0; j < m; j++) {
				if (t & (1 << (i * m + j))) bits[i][j] = 1;
				else bits[i][j] = 0;
			}
		}

		int tempSum = 0;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				if (visited[i][j]) continue;
				tempNum = 0;

				findBit(i, j, bits[i][j]);
				//cout << "temp Num :" << tempNum << "\n";
				tempSum += tempNum;
			}
		}

		maxResult = max(maxResult, tempSum);
	}

	cout << maxResult;
}