[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 종이 조각 (14391)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 종이 조각 (14391)

[문과 코린이의 IT 기록장] C++ 백준 문제풀이[BF] - 종이 조각 (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<algorithm>
using namespace std;
int arr[4][4];

int main() {
	int N, M; // 세로, 가로
	cin >> N >> M;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			scanf("%1d", &arr[i][j]);
			// cin >> arr[i][j]를 적용할 수 없음
			// 이 문제에서는 입력이 1 2 3이 아니라, 123으로 나와있기 때문에, 123이 int값으로 들어감
			// 따라서 1 2 3으로 배열에 각각 넣고 싶으면 scanf를 사용해 %1d를 사용해야 한다. (1은 1글자라는 의미)
			// scanf에서 %d로 받게 되면, cin과 마찬가지로 int형 123을 받게 됨.
		}
	}

	int ans = -1; // 최종 정답 (연결된 조각들의 합의 최대값)
	// 0 : ㅡ  
	// 1 : |

	for (int s = 0; s < (1 << (N * M)); s++) // 경우의 수는 1<< (N*M)가지
		// 0,1로 순서를 정해주는 것 s=0이면 모두 가로인 것, s=1이면 마지막만 세로인 것
	{
		int sum = 0;
		// 연결된 조각들의 합


		/* 가로 연결 부분의 경우 */
		for (int i = 0; i < N; i++) // N : 세로
		{
			int cur = 0; // 가로로 연결될 경우

			for (int j = 0; j < M; j++) // M : 가로
			{
				int k = i * M + j;
				// k는 0번째 가로줄부터, M번째 가로줄까지 하나씩 검사해나감 (가로로 검사해나감)

				// 해당 위치가 1인지, 0인지 검사.
				if ((s & (1 << k)) == 0)
					// 해당위치가 0일 경우 (가로일 경우)
				{
					cur = cur * 10 + arr[i][j];
				}
				else
				{
					sum += cur; // 가로 끝났다는 의미로, 최종 합에 더해주기
					cur = 0; // cur를 0으로 초기화
				}
			}
			sum += cur; // 마지막(M번째)이 가로일 수도 있으므로, cur 더해주기
		}

		/* 세로 연결 부분의 경우 */
		for (int j = 0; j < M; j++) // M : 가로
		{
			int cur = 0;

			for (int i = 0; i < N; i++) // N : 세로
			{
				int k = i * M + j;
				// k는 0번째 세로줄부터, N번째 세로줄까지 하나씩 검사해나감 (아래로 검사해나감)

				if ((s & (1 << k)) != 0) // 해당 위치가 1일 경우 (세로일 경우)
				{
					cur = cur * 10 + arr[i][j];
				}
				else
				{
					sum += cur; // 세로가 끝났다는 의미로, 최종 합에 더해주기.
					cur = 0; // cur을 초기화
				}
			}
			sum += cur; // 마지막(N번째)가 세로일 수 있으므로, cur 더해주기
		}


		/* 현재 조각의 합과, 기존 조각의 최대값 비교 */
		// 현재까지 나온 sum이 이 순서의 경우 나오는 조각의 합
		ans = max(ans, sum); // 더 큰 값을 저장.
	}

	cout << ans << '\n';

	return 0;
}