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

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

14391번: 종이 조각

🔔 문제 : 

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어집니다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어집니다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나입니다.

 

종이를 잘라서 얻을 수 있는 점수의 최댓값을 출력합니다. 종이는 직사각형을 겹치지 않는 조각으로 잘라야합니다.

쉽게 생각하면 대각선 방향을 제외한 가로 세로로 원하는 만큼 자른다고 생각하면 됩니다.

---

🔔 Kick Point :

처음에는 가장 긴 줄만 더하면 풀 수 있을줄 알았는데 여러가지 반례사항이 있어서 안되더라구요,

따라서 N,M이 4이하이기 때문에 브루탈포스로 하나하나 일일히 풀었습니다.

 

저는 위 종이 조각에 가로 세로로 나눌때 조합을 이용하여 

가로인 종이조각 갯수가 0일때부터 (N*M)일 때 까지 전부 구했습니다. (가로만 구하면 그 외는 모두 세로 입니다.)

 

가로와 세로 조각으로 나눴다면, 코딩을 이용하여 최댓값을 구하는건 어떻게든 할 수 있더라구요

 

코드 순서를 정리해보면

1. DFS를 이용해 N*M 종이조각에 가로와 세로로 구분짓는다. (이때 저는 세로는 0, 가로는 1,  -1은 접근불가로 했습니다)

2. 가로로 연속된 종이조각의 숫자들을 모두 더한다.

3. 세로로 연속된 종이조각의 숫자들을 모두 더한다.

4. 최댓값을 비교해가며, 숫자가 크면 최댓값을 새로 갱신한다.

5. 가로의 갯수를 0부터 N*M개 까지 DFS 반복한다.

 

---

🔔 Code :

변수

Num[4][4] : 종이조각 숫자

Marked[4][4] : 접근불가 = -1, 가로 = 1, 세로 = 0 (Check[16]의 값을 2차원 배열로 보기 편하게 바꾼 변수입니다.)

Check[16] = DFS을 통해 가로, 세로로 나누는 변수

N = 가로갯수, M = 세로 갯수, K = N*M

Res = 최댓값

 

함수

Input : Num[4][4]에 숫자를 채워넣어줌, 이때 한줄씩 들어오기에 string Inp를 이용하여 문자 한개씩으로 숫자를 넣어줌.

Marking : 가로 세로의 구분하는 변수 Marked[4][4] 에 1차원 배열 Check를 보기 편하게 2차원 배열로 바꿔줌

Marked_reset : DFS 계산이 끝날때마다 Marked[4][4] 변수에 -1로 숫자를 리셋시켜줌.

Solve :  종이조각 숫자별로 값을 더함.

isNext: 다음 숫자가 연속된 가로인지, 세로인지를 알려주는 함수

 

 

 

#include <iostream>
#include <string>
using namespace std;

int Num[4][4];
int Marked[4][4]; // -1: 접근 불가 0 : 세로, 1 : 가로
bool Check[16] = { false , }; // nCm을 선택  ex) 3x2 면 6까지만 사용
int N, M, K;
int Res = -1; // 최대값 구하기,, 
	

// 배열 Marked 를 모두 -1로 바꾸기
void Marked_reset() {
	fill(&Marked[0][0], &Marked[3][4], -1);
}


// N*M grid인 Num에 숫자 넣기
void Input() {
	Marked_reset(); 

	cin >> N >> M;
	K = N * M;

	for (int i = 0; i < N; i++)
	{
		string Inp; cin >> Inp;
		for (int j = 0; j < Inp.length(); j++)
		{
			Num[i][j] = Inp[j] - '0';
		}
	}
}

// 배열 Marking 에 가로 세로 추가
void Marking() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			Marked[i][j] = Check[(j + M * i)];
		}
	}
}

// row : true, column : false
int isNext(int n, int m, bool row_column) {
	int tmp = 10;
	if (row_column) {

		if (m == 3) return 1;

		if (Marked[n][m + 1] == 1) {
			return tmp * isNext(n, m + 1, row_column);
		}
		else {
			return 1;
		}

	}
	else {
		
		if (n == 3) return 1;

		if (Marked[n + 1][m] == 0) {
			return tmp * isNext(n + 1, m, row_column);
		}
		else {
			return 1;
		}
	}



}

// 가로 세로 별로 값 구하기
int Solve() {

	int row = 0;
	int column = 0;
	
	// 값 구하기
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			
			// 가로
			if (Marked[i][j] == 1) {
				row += Num[i][j] * isNext(i, j, true);
			}

			// 세로
			else if (Marked[i][j] == 0) {
				column += Num[i][j] * isNext(i, j, false);
			}
		}
	}

	return row + column;
}

void DFS(int dest, int cnt = 0, int n = 0) {
	if (cnt == dest) {
		int total;
		
		Marking();
		total = Solve();
		Marked_reset();

		if (Res < total) {	Res = total;}
		
		return;
	}

	for (int i = n; i < K; i++) {
		if (!Check[i]) {
			Check[i] = true;
			DFS(dest, cnt + 1, i + 1);
			Check[i] = false;
		}
	}
}



int main() {
	Input();

	for (int i = 0; i <= K; i++) {
		DFS(i);
	}

	cout << Res;

}

---