종이조각

후기

일단 시간안에 다 못 풂.

4X4일 경우 도대체 어떻게 나누어야할지를 갈피를 못잡음

문제 이해가 안가는 부분이 행부분 쭉 다 더한거랑 열부분 쭉 다 더한거랑 비교해서 큰게 가장 크게 종이 조각을 나눈거 아닌가? 라는 생각이 드는데...

숫자 0이 있기 때문에 안된다.

이런경우 행부분 4칸으로

이거 자르면 4자리수로 표현을 해야하는데 행은 왼쪽부터 읽는 규칙이 있기 때문에 10이기때문에 이런식으로는 못자름.

따라서 문제를 풀 때 자기만의 "규칙"을 가지고 풀어야한다.

0은 가로 1은 세로로 생각 한다는 규칙

이런식으로 생각을 해야한다.

"약속""을 정해서 푸는 "아이디어"가 필요하다.

4 * 4 행렬일때 1칸안에 들어가는 모든 경우의 수를 2진수로 표현이 가능하다.

그 표현의 경우의 수마다 0과 1을 싹다 찾아서 max값을 구해준다.

3*3일 경우

이런경우 수를 쫙피면은

36이다.

그리고 여기에 0이 연속적으로 몇개가 있는지 찾고

1이 세로로 몇개가 있는지 찾는 것이다.

// n * m = 모든 경우의 수 
for (int s = 0; s < (1 << n * m); ++s)
{
	// 여기서 부터 아래 코드는 '0'을 확인하는 Logic 
	int sum = 0;
	for (int i = 0; i < n; ++i)
	{
		int cur = 0;
		for (int j = 0; j < m; ++j)
		{
			int k = i * m + j;
			if ((s & (1 << k)) == 0) cur = cur * 10 + a[i][j];
			else 
			{
				sum += cur; 
				cur = 0;
			}
		}
		sum += cur;

이게 가로의 0을 찾는 로직이다.

k는

이런식으로 채워진다. 이 수들을 s와 비트 연산자를 사용해서 값을 비교를 한다.

이런경우

int k = i * m + j;
if ((s & (1 << k)) == 0) cur = cur * 10 + a[i][j];
else 
{
	sum += cur; 
	cur = 0;
}

비트가 1 << k 한것과 참이라는 값이 나오면 해당 행/열 의 값을 cur에다가 더해준다.

이작업을 1이 나오기 전까지 반복을 하다가 1이 나오면 else로 빠진다음에 sum에다 값을 더해준뒤 cur값은 0으로 초기화 후 다시 로직을 실행한다.

마찬가지로 열부분도 똑같이 진행을 해준다.

다시 분석

• 전역변수는 초기화 할 필요 없다
• 비트연산자 우선순위를 생각해야한다
• 1 << n m 이 아니라 1 << (n m) 이여야한다.

cpp

#include <bits/stdc++.h>
using namespace std;

// 백준 14391
#define endl "\n"

int n, m, a[4][4], ret = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
	{
		for (int j = 0; j < m; ++j)
		{
			scanf("%1d", &a[i][j]);
		}
	}
	 ) 
    // 이거 1 << (n * m) 
	for (int s = 0; s < (1 << (n * m)); ++s)
	{ 
		int sum = 0;
		for (int i = 0; i < n; ++i)
		{
			int cur = 0;
			for (int j = 0; j < m; ++j)
			{
				int k = i * m + j;
				// cur값은 7 -> 71 -> 711 이런식으로 감. 
				if ((s & (1 << k)) == 0) 
				{
					cur = (cur * 10) + a[i][j]; 
				}
				// 1이 나오는 경우 
				else 
				{
					sum += cur; 
					cur = 0;
				}
			}
			sum += cur;
		}
		
		// '1'을 확인하는 Logic (세로) 
		for (int j = 0; j < m; ++j)
		{
			int cur = 0;
			for (int i = 0; i < n; ++i)
			{
				int k = i * m + j;
				if ((s & (1 << k)) != 0)
				{
					cur = cur * 10 + a[i][j];
				}
				else 
				{
					sum += cur;
					cur = 0;
				}
			}
			sum += cur;
		}
		
		ret = max(ret, sum);
	}
	
	cout << ret << endl;

	return 0;
}