이번에는 백준 14391번 종이 조각 문제를 풀어보았습니다.
문제를 처음 봤을 때 각 칸이 가로 조각에 포함될지, 세로 조각에 포함될지만 결정하면 된다고 생각했습니다.
종이의 최대 크기가 4×4이므로 총 16칸이고, 각 칸마다 두 가지 선택만 존재하기 때문에 모든 경우를 완전탐색하여 해결할 수 있다고 생각했습니다.
각 칸을 가로 또는 세로로 표시한 뒤, 현재 상태에서 만들어지는 숫자들의 합을 계산하도록 구현하였습니다.
문제 설명
종이를 여러 개의 가로 또는 세로 조각으로 나누어야 합니다.
가로 조각은 왼쪽에서 오른쪽으로 숫자를 이어 붙이고,
세로 조각은 위에서 아래로 숫자를 이어 붙입니다.
모든 조각의 합이 최대가 되도록 하는 값을 구하는 문제입니다.
풀이 아이디어
각 칸을 두 가지 상태로 나누었습니다.
- 0 : 가로 조각
- 1 : 세로 조각
모든 칸의 상태를 결정한 뒤 현재 상태에서 가로 조각들의 합과 세로 조각들의 합을 계산하였습니다.
가로를 계산할 때 세로 조각을 만나면 지금까지 만든 숫자를 더하고 다시 시작하였습니다.
세로 역시 같은 방식으로 계산하였습니다.
모든 경우를 탐색하면서 가장 큰 값을 정답으로 사용하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int N,M;
bool selected[16];
int arr[4][4];
int ret = INT_MIN;
int calculate() {
int sum = 0;
for (int i=0; i<N; i++) {
string s = "";
for (int j=0; j<M; j++) {
if (selected[i*M + j]) {
if (s == "") continue;
else {
sum += stoi(s);
s = "";
continue;
}
}
s += to_string(arr[i][j]);
}
if (s == "") continue;
sum += stoi(s);
}
for (int j = 0; j < M; j++) {
string s = "";
for (int i = 0; i < N; i++) {
if (!selected[i*M + j]) {
if (s == "") continue;
else {
sum += stoi(s);
s = "";
continue;
}
}
s += to_string(arr[i][j]);
}
if (s == "") continue;
sum += stoi(s);
}
return sum;
}
void solve(int num) {
if (num == N * M) {
ret = max(ret, calculate());
return;
}
solve(num+1);
selected[num] = true;
solve(num+1);
selected[num] = false;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
cin >> N >> M;
for (int i = 0; i < N; i++) {
string s;
cin >> s;
for (int j = 0; j < M; j++) {
arr[i][j] = s[j] - '0';
}
}
solve(0);
cout << ret << '\n';
return 0;
}풀이 흐름
- 종이의 숫자를 입력받습니다.
- 모든 칸에 대해 가로 또는 세로 여부를 선택합니다.
- 모든 칸의 선택이 끝나면 현재 상태의 합을 계산합니다.
- 가로 조각들의 합을 계산합니다.
- 세로 조각들의 합을 계산합니다.
- 최댓값을 갱신합니다.
- 모든 경우를 탐색한 뒤 결과를 출력합니다.
구현 포인트
1. 각 칸의 상태 저장
각 칸을 가로 또는 세로 조각으로 사용할지를 selected 배열에 저장하였습니다.
bool selected[16];2차원 배열을 1차원으로 표현하기 위해
i * M + j를 이용하여 인덱스를 관리하였습니다.
false: 가로 조각true: 세로 조각
2. 모든 경우 탐색
각 칸마다 두 가지 선택을 수행하였습니다.
solve(num+1);
selected[num] = true;
solve(num+1);
selected[num] = false;총 2^(N×M)개의 상태를 모두 탐색하도록 구현하였습니다.
3. 가로 조각 계산
가로 방향으로 탐색하면서 숫자를 문자열로 이어 붙였습니다.
s += to_string(arr[i][j]);세로 조각을 만나면 현재까지 만든 숫자를 더하고 다시 시작하였습니다.
if (selected[i*M + j]) {
if (s == "") continue;
sum += stoi(s);
s = "";
continue;
}행의 끝까지 도달한 경우에도 마지막 숫자를 더하였습니다.
if (s != "")
sum += stoi(s);4. 세로 조각 계산
세로도 같은 방식으로 계산하였습니다.
if (!selected[i*M + j]) {
if (s == "") continue;
sum += stoi(s);
s = "";
continue;
}가로 조각을 만나면 지금까지 만든 숫자를 더하고 다시 시작하도록 구현하였습니다.
5. 최댓값 갱신
모든 칸의 선택이 끝난 경우 현재 점수를 계산하였습니다.
if (num == N * M) {
ret = max(ret, calculate());
return;
}모든 경우를 탐색한 뒤 가장 큰 값을 정답으로 사용하였습니다.
