문제
핵심
- 입력의 크기가 이라 구현에 초점을 맞춘다.
- 쉽게 말해 정사각형 4개를 이어 붙인 도형에 해당하는 최고 점수를 구해야 한다. 이 도형의 모양은 5가지가 있으며 회전과 대칭이 가능하다.
- 5개 모형을 시계 방향으로 회전하면서 대칭할 경우와 모양이 달라지는 경우를 모두 구하여 배열에 담는다. 왼쪽 상단 도형을 1번 도형이라고 할 때, 1번 도형은 모양이 대칭이므로 한 번 회전한 경우에만 달라진 모양을 추가한다. 2번 도형은 대칭과 회전 모두 달라지는 경우가 없다. 3, 4, 5번은 90도씩 회전시키며 모양이 달라질 경우 추가한다. 회전시키며 대칭 모양이 다른 경우도 추가한다. 코드로 표현하면 다음과 같다.
vector<vector<vector<int>>> shape {
{{1, 1, 1, 1}},
{{1},{1},{1},{1}},
{{1, 1}, {1, 1}},
{{1, 0}, {1, 0}, {1, 1}},
{{0, 1}, {0, 1}, {1, 1}},
{{1, 1, 1}, {1, 0, 0}},
{{1, 1, 1}, {0, 0, 1}},
{{1, 1}, {0, 1}, {0, 1}},
{{1, 1}, {1, 0}, {1, 0}},
{{0, 0, 1}, {1, 1, 1}},
{{1, 0, 0}, {1, 1, 1}},
{{1, 0}, {1, 1}, {0, 1}},
{{0, 1}, {1, 1}, {1, 0}},
{{0, 1, 1}, {1, 1, 0}},
{{1, 1, 0}, {0, 1, 1}},
{{1, 1, 1}, {0, 1, 0}},
{{0, 1}, {1, 1}, {0, 1}},
{{1, 0}, {1, 1}, {1, 0}},
{{0, 1, 0}, {1, 1, 1}}
};- 하드 코딩되어 있지만 문제는 굉장히 직관적으로 풀 수 있다. shape 배열의 크기는 도형의 개수를 의미하고, shape[index]의 크기는 해당 도형의 높이를 의미한다. shape[index][0]은 해당 너비를 의미한다. 따라서 종이의 각 점에서 해당 도형을 놓을 수 있는지 해당 도형의 높이와 너비를 통해 파악할 수 있다. 종이에 도형을 놓을 수 있다면 도형에서 숫자 1로 채워진 부분만 점수를 더하면 된다.
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < (int)shape.size(); ++k) {
checkScore(k, i, j);
}
}
}
void checkScore(int index, int y, int x) {
int r = shape[index].size();
int c = shape[index][0].size();
if (y + r > n || x + c > m)
return ;
int score = 0;
for (int i = y; i < y + r; ++i) {
for (int j = x; j < x + c; ++j) {
if (shape[index][i - y][j - x] == 1)
score += paper[i][j];
}
}
ans = max(ans, score);
}개선
- 해당 코드로도 깔끔하게 통과할 수 있지만, 해당 문제를 DFS로 풀 수 있어서 소개한다. 해당 문제를 DFS로 접근하기 까다로운 이유는 한 칸씩 이동하며 칸을 추가할 때 5번 도형을 추가하는 게 애매하기 때문이다. 왜냐하면 3번째 정사각형을 선택했을 때 4번째 정사각형이 붙어있지 않기 때문이다. 따라서 3번째 정사각형을 선택할 때, 2번째 정사각형에서 상, 하, 좌, 우 에 있는 정사각형 2개를 선택하면 5번 도형을 회전하거나 대칭했을 경우를 포함한 경우를 고려할 수 있다.
#include <iostream>
#include <vector>
using namespace std;
int n, m;
int dy[] = {-1, 0, 1, 0};
int dx[] = {0, 1, 0, -1};
int paper[504][504];
bool isVisited[504][504];
int ans = 0;
void dfs(int depth, int y, int x, int sum) {
if (depth == 4) {
ans = max(ans, sum);
return;
}
for (int dir = 0; dir < 4; ++dir) {
int ny = y + dy[dir];
int nx = x + dx[dir];
if (ny < 0 || ny >= n || nx < 0 || nx >= m) continue;
if (isVisited[ny][nx]) continue;
sum += paper[ny][nx];
isVisited[ny][nx] = true;
dfs(depth + 1, ny, nx, sum);
if (depth == 2)
dfs(depth + 1, y, x, sum);
sum -= paper[ny][nx];
isVisited[ny][nx] = false;
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
cin >> paper[i][j];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
isVisited[i][j] = true;
dfs(1, i, j, paper[i][j]);
isVisited[i][j] = false;
}
}
cout << ans;
}코드
시간복잡도
C++
#include<iostream>
#include <vector>
using namespace std;
int n, m;
int paper[504][504];
int ans = 0;
vector<vector<vector<int>>> shape {
{{1, 1, 1, 1}},
{{1},{1},{1},{1}},
{{1, 1}, {1, 1}},
{{1, 0}, {1, 0}, {1, 1}},
{{0, 1}, {0, 1}, {1, 1}},
{{1, 1, 1}, {1, 0, 0}},
{{1, 1, 1}, {0, 0, 1}},
{{1, 1}, {0, 1}, {0, 1}},
{{1, 1}, {1, 0}, {1, 0}},
{{0, 0, 1}, {1, 1, 1}},
{{1, 0, 0}, {1, 1, 1}},
{{1, 0}, {1, 1}, {0, 1}},
{{0, 1}, {1, 1}, {1, 0}},
{{0, 1, 1}, {1, 1, 0}},
{{1, 1, 0}, {0, 1, 1}},
{{1, 1, 1}, {0, 1, 0}},
{{0, 1}, {1, 1}, {0, 1}},
{{1, 0}, {1, 1}, {1, 0}},
{{0, 1, 0}, {1, 1, 1}}
};
void checkScore(int index, int y, int x) {
int r = shape[index].size();
int c = shape[index][0].size();
if (y + r > n || x + c > m)
return ;
int score = 0;
for (int i = y; i < y + r; ++i) {
for (int j = x; j < x + c; ++j) {
if (shape[index][i - y][j - x] == 1)
score += paper[i][j];
}
}
ans = max(ans, score);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j)
cin >> paper[i][j];
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
for (int k = 0; k < (int)shape.size(); ++k) {
checkScore(k, i, j);
}
}
}
cout << ans;
}Java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int n, m;
static int[][] paper = new int[504][504];
static int ans = 0;
static int[][][] shape = {
{{1, 1, 1, 1}},
{{1}, {1}, {1}, {1}},
{{1, 1}, {1, 1}},
{{1, 0}, {1, 0}, {1, 1}},
{{0, 1}, {0, 1}, {1, 1}},
{{1, 1, 1}, {1, 0, 0}},
{{1, 1, 1}, {0, 0, 1}},
{{1, 1}, {0, 1}, {0, 1}},
{{1, 1}, {1, 0}, {1, 0}},
{{0, 0, 1}, {1, 1, 1}},
{{1, 0, 0}, {1, 1, 1}},
{{1, 0}, {1, 1}, {0, 1}},
{{0, 1}, {1, 1}, {1, 0}},
{{0, 1, 1}, {1, 1, 0}},
{{1, 1, 0}, {0, 1, 1}},
{{1, 1, 1}, {0, 1, 0}},
{{0, 1}, {1, 1}, {0, 1}},
{{1, 0}, {1, 1}, {1, 0}},
{{0, 1, 0}, {1, 1, 1}}
};
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
n = Integer.parseInt(st.nextToken());
m = Integer.parseInt(st.nextToken());
for (int i = 0; i < n; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < m; j++) {
paper[i][j] = Integer.parseInt(st.nextToken());
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
for (int k = 0; k < shape.length; k++) {
checkScore(k, i, j);
}
}
}
System.out.println(ans);
}
static void checkScore(int index, int y, int x) {
int r = shape[index].length;
int c = shape[index][0].length;
if (y + r > n || x + c > m)
return;
int score = 0;
for (int i = y; i < y + r; ++i) {
for (int j = x; j < x + c; ++j) {
if (shape[index][i - y][j - x] == 1)
score += paper[i][j];
}
}
ans = Math.max(ans, score);
}
}
- 하드 코딩한 코드가 DFS 풀이보다 조금 더 빠른 것을 확인할 수 있다.
꾸준하게