[코드트리] 최고의 33위치 [C/C++] for 코드트리 조별과제

풀이

N * N 격자에서 3 * 3 범위에 존재하는 1의 최대갯수를 구하는 문제다.

N이 20으로 작으니 윈도우 슬라이싱없이 모든 경우를 계산해도 충분하다.

격자 정보를 입력받은 후에 1 ~ N - 2 범위를 탐색해주자.

1 ~ N - 2 범위내의 (i, j)에 대해 (i ~ i + 2, j ~ j + 2)로 만들어지는 3 * 3 범위 내 1이 몇개 존재하는지 구하자.

만약 이전 범위보다 갯수가 많다면 최댓값으로 갱신해주자. 만약 1의 갯수가 9라면 주어진 문제에서 가질 수 있는 최댓값 이므로 탐색을 중단하자.

---

소스코드

보기

---

출처

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석