https://www.acmicpc.net/problem/14391
종이를 여러 조각으로 잘라서 합을 구하는 문제
1차 풀이 방법 - 시간 초과
dfs
각 칸에서 가로길이, 세로길이 가능한 만큼 확인하고 dfs로 다음 칸으로 넘어간다.
n,m 이 4,4 일 때 한 칸에서 고려하는 경우의 수 = (가로 0,1,2,3) + (세로 0,1,2,3) = 8
탐색할수록 경우의 수는 줄어들긴 하지만 경우가 제곱으로 커짐
또한 계산하지 않아도 되는 경우까지 계산하게 됨.
-> 한 줄에 가로2칸 + 가로2칸 이면 따로 계산하는게 아니라
가로4칸으로 계산해서 하나로 이은 값이 더 크다.
2차 풀이 방법 - 정답
마찬가지로 dfs 이지만
각 칸을 가로칸으로 배치할 것인지 세로칸으로 배치할 것인지 정한다.
모든 칸을 전부 정했으면 붙어있는 칸이 같은칸이면 자릿수를 올려가며 더해주기.
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb;
static StringTokenizer st;
static int n, m, count, max = Integer.MIN_VALUE;
static int[][] arr;
static int[][] visited;
// 오른쪽, 아래쪽만 고려
static int[] dx = {1, 0};
static int[] dy = {0, 1};
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new int[n][m];
for (int i = 0 ; i < n ; i ++) {
String str = br.readLine();
for (int j = 0 ; j < m ; j ++) {
arr[i][j] = str.charAt(j) - '0';
visited[i][j] = -1;
}
}
dfs(0, 0, 0, 0);
System.out.println(max);
}
static void dfs(int depth, int sum, int x, int y) {
// 모든 칸을 전부 확인 했으면 합 계산
if (depth == n * m) {
if (sum > max) max = sum;
return;
}
for (int i = x ; i < n ; i ++) {
for (int j = (i == x ? y : 0) ; j < m ; j ++) {
if (visited[i][j] == -1) {
// 세로로 얼마나 갈 지 정해서 가기
for (int h = 0 ; h < n - i ; h ++) {
// 이미 다른 종이 조각이 있으면 안됨.
if (avail(i, j, h, 0)) {
int val = chkLine(i, j, h, 0, count++);
dfs(depth + h + 1, sum + val, i, j);
chkLine(i, j, h, 0, -1);
count --;
}
}
// 가로로 얼마나 갈 지
for (int w = 0 ; w < m - j ; w ++) {
if (avail(i, j, w, 1)) {
int val = chkLine(i, j, w, 1, count++);
dfs(depth + w + 1, sum + val, i, j);
chkLine(i, j, w, 1, -1);
count --;
}
}
}
}
}
}
// 갈 수 있는곳인지 검증하고 들어와야 함.
// dir: 0 => 아래쪽, dir: 1 => 오른쪽
static int chkLine(int x, int y, int len, int dir, int count) {
int sum = 0;
int temp = (int)Math.pow(10, len);
for (int i = 0 ; i < len + 1 ; i ++) {
int nx = x + dx[dir] * i;
int ny = y + dy[dir] * i;
visited[nx][ny] = count;
sum += arr[nx][ny] * temp;
temp /= 10;
}
return sum;
}
static boolean avail(int x, int y, int len, int dir) {
for (int i = 0 ; i < len + 1 ; i ++) {
int nx = x + dx[dir] * i;
int ny = y + dy[dir] * i;
if (visited[nx][ny] != -1) return false;
}
return true;
}
}
import java.util.*;
import java.io.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int n, m, max = 0;
static int[][] arr;
static boolean[][] visited;
public static void main(String[] args) throws IOException {
st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
arr = new int[n][m];
visited = new boolean[n][m];
for (int i = 0; i < n; i++) {
String str = br.readLine();
for (int j = 0; j < m; j++) {
arr[i][j] = str.charAt(j) - '0';
}
}
dfs(0, 0);
System.out.println(max);
}
// 각 칸에 대해 가로/세로 선택
static void dfs(int x, int y) {
if (x == n) {
calc();
return;
}
int nextX = x;
int nextY = y + 1;
if (nextY == m) {
nextX++;
nextY = 0;
}
// 가로 조각으로 선택
visited[x][y] = true;
dfs(nextX, nextY);
// 세로 조각으로 선택
visited[x][y] = false;
dfs(nextX, nextY);
}
// 종이 조각 합계 계산
static void calc() {
int sum = 0;
// 가로 조각 계산
for (int i = 0; i < n; i++) {
int temp = 0;
for (int j = 0; j < m; j++) {
if (visited[i][j]) { // 가로 조각
temp = temp * 10 + arr[i][j];
} else {
sum += temp;
temp = 0;
}
}
sum += temp; // 줄 끝나면 더하기
}
// 세로 조각 계산
for (int j = 0; j < m; j++) {
int temp = 0;
for (int i = 0; i < n; i++) {
if (!visited[i][j]) { // 세로 조각
temp = temp * 10 + arr[i][j];
} else {
sum += temp;
temp = 0;
}
}
sum += temp; // 줄 끝나면 더하기
}
max = Math.max(max, sum);
}
}