[백준 14391] 종이 조각 (C++)

문제 링크: www.acmicpc.net/problem/14391

14391번: 종이 조각

 

1. 주의할 점

- 최대 4*4이므로, 브루트포스 알고리즘을 사용한다

- 사용한 숫자처리를 제대로 하면 된다

 

2. 구현

- 배열을 입력받은 후, 왼쪽위 원소부터 브루트포스를 수행한다

- 브루트포스는 다음과 같은 순서로 진행된다. 해당 원소만 포함, 해당 원소포함 + 아래숫자들 포함, 해당 원소포함 + 오른쪽 숫자들 포함

- 단, 위의 기준은 항상 추가할 숫자가 방문처리되어 있지 않다는 가정하에 진행한다.

- 해당 원소를 기준으로 위의 3가지 조건 중 1개를 수행했을 경우, 다음 브루포스 함수 호출은 항상 Brute(Num+1, Sum+Val)로 한다. 이에 따라, 2번째 조건인 해당 원소포함 + 아래숫자들 포함 을 수행할 경우, Check[][]배열을 확인하지 않아도 된다는 사실 또한 알 수 있다(이해 안가면 구현한 로직이 어떤 방식으로 작동하는지 파악해보세요)

 

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int arr[4][4];
bool check[4][4] = { false, };
int row, col, result = 0;

void brute(int num, int sum) {
	int x = num % col;
	int y = num / col;
	if (num >= row * col) {
		result = max(result, sum);
		return;
	}
	if (check[y][x]) brute(num + 1, sum);
	else {
		int val, ny, nx;
		val = arr[y][x];
		check[y][x] = true;
		brute(num + 1, sum + val);
		check[y][x] = false;
		//밑으로
		for (int k = 1; k < row - y; k++) {
			nx = x;
			ny = y + k;
			val *= 10;
			val += arr[ny][nx];
			for (int j = 1; j <= k; j++)
				check[y + j][nx] = true;
			brute(num + 1, sum + val);
			for (int j = 1; j <= k; j++)
				check[y + j][nx] = false;
		}
		val = arr[y][x];
		//오른쪽으로
		for (int k = 1; k < col - x; k++) {
			ny = y;
			nx = x + k;
			if (check[ny][nx]) return;
			val *= 10;
			val += arr[ny][nx];
			for (int j = 1; j <= k; j++)
				check[ny][x+j] = true;
			brute(num + 1, sum + val);
			for (int j = 1; j <= k; j++)
				check[ny][x + j] = false;
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> row >> col;
	string str;
	for (int i = 0; i < row; i++) {
		cin >> str;
		for (int j = 0; j < col; j++)
			arr[i][j] = str[j] - '0';
	}
	brute(0, 0);
	cout << result;
	return 0;
}