비트마스크 기법으로 풀 수 있지만 아직 dfs가 편한 관계로 dfs 알고리즘으로 풀었다.
생각할 포인트
- 각 숫자마다 가로로 자를지 세로로 자를지에 대한 경우의 수 두 가지가 나온다.
- 전체 조합은 1번에 따라서 여러 가지가 나온다. ( 정확히는 2에다가 칸 수를 제곱한만큼 나온다.)
- 가로로 잘랐을 때와 세로로 잘랐을 때의 종이 조각의 합을 다르게 구한다.
우선 종료 시점부터 생각해보자.
0 번째 행부터 N-1 번째 행까지 둘러보고 행이 N 번째가 되면 더 이상 탐색할 곳이 없으므로 종료한다.
다음으로 1번을 생각해보자 입력 받은 숫자 배열을 탐색하며 이 숫자를 가로로 자를지 세로로 자를지를 boolean 배열에 입력해서 저장한다. true 는 가로로 false 는 세로로 정해서 풀었다.
다음으로 2번을 시행하자.
모든 숫자 배열을 돌면서 각 숫자 배열을 가로로 자를지 세로로 자를지 선택하고 다음 숫자 배열로 넘어간다.
코드를 보자.
public static void dfs(int x, int y) {
//
if (x == N) {
// 모든 종이를 다 어떻게 자를지 선택한 뒤 이때의 합을 구한다.
sum();
return;
}
// 가장 오른쪽까지 왔으므로 다음 행 제일 왼쪽으로 넘겨준다.
if (y == M) {
// 다음 행으로 이동
dfs(x + 1, 0);
return;
}
// 모든 숫자배열을 탐색하면서 가로로 자를지 세로로 자를지 선택해서 boolean 배열에 저장한다.
// sliceArr = new boolean[N][M]
// 가로로 자르는 것을 선택 = true
sliceArr[x][y] = true;
// 오른쪽에 있는 숫자로 넘어간다.
dfs(x, y + 1);
// 세로로 자르는 것을 선택 = false
sliceArr[x][y] = false;
// 오른쪽에 있는 숫자로 넘어간다.
dfs(x, y + 1);
}다음으로 가로로 잘랐는지 세로로 잘랐는지에 따라 달라지는 합을 구하는 방법을 보자.
우선 이 자른 경우의 수의 합을 result 라는 변수에 0으로 초기화를 해준다.
그 다음 가로로 자른 종이 조각의 합을 구한다.
각 행마다 temp 라는 이번의 가로 종이 조각의 합을 담는 변수를 0으로 초기화 하고 시작한다.
가로로 잘랐기에 오른쪽으로 한칸씩 넘어가며 sliceArr에 담긴 이번 종이 조각의 잘린 방향을 본다.
이때 가로로 잘린 종이면 현재 가로 종이 조각의 합을 x10 해준다.
여기서 예시를 보자면 2 3 5 칸의 가로 종이 조각이 있다고 해보자.
우선 temp 는 0 부터 시작하다가 2 칸을 만난다.
2 칸의 sliceArr 값을 살펴보니 true 즉, 가로 종이다.
현재 temp 는 0 이기에 x10 을 해줘도 0이다.
그 후 temp에 2를 더해준다. 현재 temp는 2이다.
다음 3 칸을 만났고 가로로 잘린 종이다. 현재 temp=2 에 x10을 해준다.
temp는 현재 20 즉, 전의 가로 종이의 자릿수가 계산된다. 그 후 3을 더해주니 23이 된다.
그 다음 5 칸을 똑같이 따라가다보면 235 라는 temp를 얻게 된다.
그 후 가로 종이가 아닌 것을 만나거나 다음 행으로 넘어가면 temp를 현재의 경우의 수의 합 result에 더해주고 0 으로 초기화 해준다.
세로로 자른 종이의 합을 구하는 방법은 행부터 보지말고 열부터 보면서 아래쪽으로 내려가면서 탐색하여 구하면 된다.
코드를 보면 이해하기 쉽다.
// 조각난 종이의 합 구하는 함수
public static void sum() {
int result = 0;
int temp;
// 가로로 자른 종이들 합 구하기
for (int i = 0; i < N; i++) {
temp = 0;
for (int j = 0; j < M; j++) {
// 가로로 자른 종이일 때
if (sliceArr[i][j]) {
temp *= 10;
temp += numArr[i][j];
}
// 가로로 자른 종이가 아닐때
else {
// 전에 구한 가로로 자른 종이의 합을 최종 합 더해줌
result += temp;
// 다시 가로 종이의 합을 0으로 초기화
temp = 0;
}
}
result += temp;
}
// 세로로 자른 종이들 합 구하기
for (int i = 0; i < M; i++) {
temp = 0;
for (int j = 0; j < N; j++) {
// 세로로 자른 종이일 때
if (!sliceArr[j][i]) {
temp *= 10;
temp += numArr[j][i];
}
// 세로로 자른 종이가 아닐때
else {
// 전에 구한 세로로 자른 종이의 합을 최종 합 더해줌
result += temp;
// 다시 세로 종이의 합을 0으로 초기화
temp = 0;
}
}
result += temp;
}
MAX = Math.max(MAX, result);
}public class bj1182 {
public static int MAX = -1;
public static int N;
public static int M;
public static int[][] numArr;
public static boolean[][] sliceArr;
public static void main(String[] args) throws Exception {
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 0이면 가로, 1이면 세로
String line = br.readLine();
String[] split = line.split(" ");
N = Integer.parseInt(split[0]);
M = Integer.parseInt(split[1]);
numArr = new int[N][M];
sliceArr = new boolean[N][M];
for (int i = 0; i < N; i++) {
String line1 = br.readLine();
char[] charArray = line1.toCharArray();
for (int j = 0; j < M; j++) {
numArr[i][j] = Integer.parseInt(String.valueOf(charArray[j]));
}
}
dfs(0, 0);
bw.write(MAX + "\n");
bw.flush();
bw.close();
br.close();
}
// 종이를 조각내는 경우의 수를 구하는 함수
public static void dfs(int x, int y) {
if (x == N) {
// 모든 종이를 다 조각냈을 때
sum();
return;
}
if (y == M) {
// 다음 행으로 이동
dfs(x + 1, 0);
return;
}
// 가로로 잘랐을 때
sliceArr[x][y] = true;
dfs(x, y + 1);
// 세로로 잘랐을 때
sliceArr[x][y] = false;
dfs(x, y + 1);
}
// 조각난 종이의 합 구하는 함수
public static void sum() {
int result = 0;
int temp;
// 가로로 자른 종이들 합 구하기
for (int i = 0; i < N; i++) {
temp = 0;
for (int j = 0; j < M; j++) {
// 가로로 자른 종이일 때
if (sliceArr[i][j]) {
temp *= 10;
temp += numArr[i][j];
}
// 가로로 자른 종이가 아닐때
else {
// 전에 구한 가로로 자른 종이의 합을 최종 합 더해줌
result += temp;
// 다시 가로 종이의 합을 0으로 초기화
temp = 0;
}
}
result += temp;
}
// 세로로 자른 종이들 합 구하기
for (int i = 0; i < M; i++) {
temp = 0;
for (int j = 0; j < N; j++) {
// 세로로 자른 종이일 때
if (!sliceArr[j][i]) {
temp *= 10;
temp += numArr[j][i];
}
// 세로로 자른 종이가 아닐때
else {
// 전에 구한 세로로 자른 종이의 합을 최종 합 더해줌
result += temp;
// 다시 세로 종이의 합을 0으로 초기화
temp = 0;
}
}
result += temp;
}
MAX = Math.max(MAX, result);
}
}