NYPC 2022 예선 | 인류의 적 모기 퇴치

[문제] 최근 이상 기후로 인해 붐힐 마을에 모기가 많이 늘어났다. 마리드는 붐힐 마을 주민들을 돕기 위해 물풍선으로 모기들을 퇴치하려고 한다. 마리드는 기존의 십자 모양의 물풍선만으로 모기를 효율적으로 퇴치할 수 없다는 것을 깨달았고, 엑스 자 모양으로 터지는 물풍선을 새로 개발했다. 붐힐 마을은 N x N 크기의 22차원 배열로 표현할 수 있고, 배열의 각 칸에 존재하는 모기의 수가 주어진다. 마리드는 한 칸을 선택하여 물풍선을 놓고 터트린다. 물풍선을 터트리면 범위 M으로 물줄기가 뻗어나가 모기를 퇴치할 수 있다. 예를 들어, 십자 모양의 경우, 물풍선을 터트린 칸에서 위쪽, 오른쪽, 아래쪽, 왼쪽의 M개 칸 이내의 모든 모기를 퇴치한다. 엑스 자 모양의 경우, 네 개의 대각선 방향으로 M개 칸 이..

2023.07.18