백준 14391 종이 조각 c++

 

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

14391번: 종이 조각

---

문제

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

입력

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

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

출력

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

---

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


int N, M;
int map[5][5];
bool check[5][5];
int result;

void dfs(int x, int y)
{
	if (x == N)//행은 N-1까지 이므로 그를 넘어가면 결과 출력
	{
		int total = 0;
		for (int row = 0; row < N; row++)
		{
			int sum = 0;
			for (int col = 0; col < M; col++)
			{
				if (check[row][col] == true)//현재칸이 true(가로)라면
				{
					sum = (sum * 10) + map[row][col];기존의 sum에 10을 곱해 현재칸 더하기
				}
				else//현재칸이 false(세로)라면
				{
					total = total + sum;//아래 세로파트에서 처리 할 것이므로 기존 sum을 total에 더하고 초기화
					sum = 0;
				}
			}
			total = total + sum;
		}
		
		//세로 구하기
		for (int col = 0; col < M; col++)
		{
			int sum = 0;
			for (int row = 0; row < N; row++)
			{
				if (check[row][col] == false)
				{
					sum = (sum * 10) + map[row][col];
				}
				else//true(가로)에 대해서는 처리 했으므로 현재까지 구한 sum을 total에 더해준다.
				{
					total = total + sum;
					sum = 0;
				}
			}
			total = total + sum;

		}
		result = max(result, total);
		total = 0;//return하기 전 초기화 하고 return
		return;
	}
	if (y == M)//열은 M-1까지 이므로 그를 넘어가면 열은 처음으로 돌리고 행 + 1
	{
		dfs(x + 1, 0);
		return;
	}
	check[x][y] = true;//현재칸이 true일 때, false일 때 한번 실행한다.
	dfs(x, y + 1);
	check[x][y] = false;
	dfs(x, y + 1);
}

int main()
{
	cin >> N >> M;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < M; j++)
		{
			scanf("%1d", &map[i][j]);
		}
	}
	dfs(0, 0);
	cout << result;
}

---

 

탐색은 이런식으로 가게 된다.

1. 열의 끝까지 닿으면 열(y)를 0으로 돌리고 행을 1추가, 이를 반복하여 행이 끝까지 다 돌았을 때 현재 dfs의 합을 계산한다.

2. dfs(행, 열 + 1) 재귀로 넘어가기 전에 현재 배열의 상태 check[x][y]를 한 번은 가로상태로(true) 한 뒤 재귀,

한 번은 세로 상태로(false) 한 뒤 재귀를 한다. 그렇게 되면 최종적으로 모든 경우의 수를 구할 수 있다.

 

3.결과 계산은 가로 세로 따로 한다.현재 칸이 true일 경우 가로처리 부분에서, false일 경우 세로 처리 부분에서 해결한다.