[백준 / BOJ] 9518 로마 카톨릭 미사

문제

출처 : www.acmicpc.net/problem/9518

9518번: 로마 카톨릭 미사

상근이가 교회 미사동안 최대한 많은사람과 악수를 하려고 한다.

 

악수는 자기 자리에서 8방향으로 할수있으며, (대각선 + 상하좌우)

상근이는 항상 가장 많은사람과 악수를 할수있는 자리에 앉는다고 할때, 미사가 진행되는동안 몇번악수를 할수있는지 구하는 문제다.

 

풀이

범위가 크지않아서 완전탐색으로 풀리는 문제였다.

주의할점이 "상근이가 악수를 하는 경우" 가 아니라 "모든 사람이 악수를 하는 경우" 를 구하는것이다.

 

1. "o"(사람이 앉아있는곳)을 입력받을때마다 8방향의 칸에 ++을 해준다.

이러면 입력이 끝났을때, 숫자가 가장 높은칸이 악수를 가장 많이 할수있는 칸이다.

(예제의 경우)

1 2 0

0 2 1

이 된다.

 

2. 1번에서 구한 걸 가지고 상근이가 앉을위치를 정해야하는데,

- 이미 사람이 앉아있지 않은곳중 가장 숫자가 높은칸을 선택해서 앉으면 된다.

 

3. 다시한번 R*S번 탐색하며, 8방향의 "o"를 가진사람이 전에 자신과 악수를 하지않았다면, 악수를 시켜준다.

(나는 "o"를 입력받을때마다 map에 {{위치Y,위치X}, o가 나온 횟수} 로 저장시켜서 체크해줬다)

 

소스코드

https://github.com/devxb/JJUNalgo/blob/master/9518%20%EB%A1%9C%EB%A7%88%20%EC%B9%B4%ED%86%A8%EB%A6%AD%20%EB%AF%B8%EC%82%AC/main.cpp

devxb/JJUNalgo