9518 로마 카톨릭 미사

9518 로마 카톨릭 미사 https://www.acmicpc.net/problem/9518

교회의 모든 사람은 인접한 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; } Colored by Color Scripter

cs