백준 - 종이조각

문제 설명

2차원 배열이 주어진다.

2차원 배열을 적절히 조각내어 자르고 만들 수 있는 최댓값을 출력한다.

같은 경계에 있으면 숫자를 이어붙이고 다른 경계에 있는 숫자는 더한다.

시도

가로로 붙일지, 세로로 붙일지 2가지의 선택한다.

풀이

static int n, m, answer;
	static int[][] paper;
	static boolean[][] v;

	public static void main(String[] args) throws IOException {
		BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(reader.readLine());
		n = Integer.parseInt(st.nextToken());
		m = Integer.parseInt(st.nextToken());
		paper = new int[n][m];
		v = new boolean[n][m];
		
		for (int i = 0; i < n; i++) {
			String str[] = reader.readLine().split("");
			for (int j = 0; j < m; j++) {
				paper[i][j] = Integer.parseInt(str[j]);
			}
		}

		dfs(0,0);

		System.out.println(answer);
	}

	private static void dfs(int y, int x) {
		if (y >= n) { // 배열 탐색 완료
			answer = Math.max(answer, sum());
			return;
		}

		if (x >= m) { // 열의 끝에 도달했을 때 다음 행으로 
			dfs(y + 1, 0);
			return;
		}

		v[y][x] = true;
		dfs(y, x + 1);
		v[y][x] = false;

		dfs(y, x + 1);
	}

	private static int sum() {
		int answer = 0;
		int temp = 0;

		for (int i = 0; i < n; i++) {
			temp = 0;
			for (int j = 0; j < m; j++) {
				if (v[i][j]) {
					temp *= 10;
					temp += paper[i][j];
				} else {
					answer += temp;
					temp = 0;
				}
			}

			answer += temp;
		}

		for (int i = 0; i < m; i++) {
			temp = 0;
			for (int j = 0; j < n; j++) {
				if (!v[j][i]) {
					temp *= 10;
					temp += paper[j][i];
				} else {
					answer += temp;
					temp = 0;
				}
			}

			answer+=temp;
		}

		return answer;
	}