[BOJ] 14391. 종이조각

* (0,0) ~ (n-1, m-1) 까지 완전 탐색하면서 백트래킹으로 전수조사를 한다. 

* 방문 표시 된 좌표는 가로로 숫자를 만드는 부분이고, 방문 표시가 안 된 부분은 세로로 숫자를 만드는 부분이다. 

	T
T	T
	T

이렇게 방문표시가 되어있다면 

 

이렇게 방문 표시가 된 부분은 가로로 직사각형을 만들고.

아닌 부분들은 세로로 직사각형을 만든다. 

 

* 이어지는 숫자를 string으로 만들어서 sum에 누적합을 해 준다. 

 

 

 

#include <iostream> #include <vector> #include <cstring> using namespace std; int n, m; char map[5][5]; int dx[2] = {1, 0}, dy[2] = {0, 1}; bool visited[5][5]; int ans = 0; bool chk[5][5]; int max(const int &a, const int &b) { if (a > b) return a; return b; } void dfs(int x, int y) { if (x == n) { //visited 처리된 것은 가로로 //아닌 것은 세로로 계산한다. string tmp = ""; int sum = 0; memset(chk, 0, sizeof(chk)); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (chk[i][j]) continue; if (visited[i][j]) { chk[i][j] = true; //가로로 연속되는 값을 구한다. if (j == m - 1) { sum += map[i][j] - '0'; } else { tmp = map[i][j]; int idx = 0; for (int k = j + 1; k < m; k++) { if (visited[i][k] && !chk[i][k]) { tmp += map[i][k]; chk[i][k] = true; } else { idx = k - 1; break; } } sum += stoi(tmp); // cout << tmp << '\n'; j = idx; } } else { chk[i][j] = true; if (i == n - 1) { sum += map[i][j] - '0'; } else { tmp = map[i][j]; for (int k = i + 1; k < n; k++) { if (!visited[k][j] && !chk[k][j]) { tmp += map[k][j]; chk[k][j] = true; } else { break; } } sum += stoi(tmp); // cout << tmp << '\n'; } } } } ans = max(ans, sum); return; } if (y >= m) { x++; y = 0; } visited[x][y] = true; dfs(x, y + 1); visited[x][y] = false; dfs(x, y + 1); } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { cin >> map[i][j]; } } dfs(0, 0); cout << ans << '\n'; return 0; }