[C++] 백준(BOJ) -14391 : 종이 조각
인프런에 있는 큰돌님의 강의 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트를 듣고 정리한 필기입니다.
문제
영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.
영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.
아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.
각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.
종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.
입력
첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)
둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.
출력
영선이가 얻을 수 있는 점수의 최댓값을 출력한다.
알고리즘
- 브루트 포스
- 비트마스킹
풀이
- 처음에는 단순히 행과 열로만 잘랐을 때 최대값이 나오지 않는가 생각해 봄
반례 :
3 4
2000
0012
0001 - 모든 경우의 수를 구하는 방법으로 선회
- n * m 의 크기가 16 이하 => 비트 마스킹으로 모든 경우의 수 구할 수 있다
- 맵을 0은 가로, 1은 세로로 나눈다는 전제 조건을 세운다
- 가로 탐색과 세로 탐색을 모두 진행하여 sum 값을 구해가며, 최대가 되는 max res값을 구한다
코드
// BOJ - 14391: 종이 조각
#include<bits/stdc++.h>
using namespace std;
int n, m, res;
int a[4][4];
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < n; i++)
{
string str;
cin >> str;
for (int j = 0; j < m; j++)
{
a[i][j] = str[j] - '0';
}
}
for (int s = 0; s < (1 << (n * m)); s++) // 맵을 0과 1로 나누는 모든 경우의 수 탐색
{
// 전체 합 초기화
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) // 0 : 가로 합
{
cur = cur * 10 + a[i][j];
}
else
{
sum += cur;
cur = 0;
}
}
sum += cur; // 남은 cur 값 sum에 더하기
}
// 가로 기준, 세로 방향 탐색
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;
}
res = max(res, sum); // 완탐 후 최대치 구하기
}
cout << res << '\n';
return 0;
}
평가
- 간단하게 행,열 나누기 후 최대값을 구하는 문제라고 생각하였지만 반례가 존재하므로 모든 경우의 수를 고려해서 풀이하여야 하는 문제이다
- 31이하의 경우의 수로 주어진 문제이므로 비트마스킹을 고려해 볼 수 있었고, 가로는 0, 세로는 1로 생각하여서 탐색 방향을 달리하여 최대값을 구해 나갈 수 있었던 문제이다
- 비트마스킹 문제 중 난이도가 좀 있었던 문제이므로 연습이 필요
