교회의 모든 사람은 인접한 8방향과의 사람과 악수를 한다.
상근이가 교회에 들어갔을 때 모든사람이 악수를 했을 때의 최댓값을 구하는 문제이다.
N이 작으므로 $O(N^4)$으로 풀 수도 있으나 $O(N^3)$의 풀이방법이 있다.
중복되게 악수하는 경우를 구하되 나중에 2로 나누면 상근이를 제외한 악수하는 경우의 수이고
앉아있는 사람들의 자리에서 인접한 빈자리로 악수할 수 있는 가장 빈번한 빈자리가 상근이가 앉으면 악수할 수 있는 최댓값이 되는 자리이다.
#include <cstdio>
#include <algorithm>
using namespace std;
int N, M;
char map[51][51];
int s[51][51];
int dy[] = { 1,0,0,-1,1, 1, -1 ,-1 };
int dx[] = { 0,-1,1,0,-1, 1, 1 ,-1 };
int main() {
scanf("%d%d", &N, &M);
for (int n = 0;n < N;n++) scanf("%s", &map[n]);
int ans = 0;
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++) {
if (map[n][m] == 'o') {
for (int i = 0;i < 8;i++) {
int ny = n + dy[i], nx = m + dx[i];
if (ny < 0 || ny >= N || nx < 0 || nx >= M) continue;
if (map[ny][nx] == 'o') ans++; //성당 사람들끼리 중복되게 악수 하는 경우
else s[ny][nx]++; //상근이가 앉는 최적 자리를 위해 누적
}
}
}
}
int ret = 0;
for (int n = 0;n < N;n++) {
for (int m = 0;m < M;m++)
ret = max(ret, s[n][m]);
}
printf("%d\n", ans / 2 + ret); //중복되게 악수하는경우 / 2, 상근이가 앉았을 때 악수하는 경우
return 0;
}
| cs |
