공터 에 대해 를 그 공터의 주변 칸에 있는 주택의 수라고 하자.
공터 에 나무를 한 그루 심으면, 그 나무는 주변에 있는 각 주택의 나무 개수에 한 번씩 포함된다. 따라서 전체 합은 정확히 만큼 증가한다. 서로 다른 공터의 기여는 서로 영향을 주지 않는다.
따라서 문제는 각 값이 이상 이하인 들 중 일부를 골라 합을 이상으로 만들면서 고른 개수를 최소화하는 문제로 바뀐다. 같은 개수의 나무를 심을 때 합을 가장 크게 만들려면 큰 부터 고르는 것이 최적이다. 그러므로 순서로 필요한 만큼 선택하면 된다.
모든 공터의 합이 보다 작으면 조건을 만족할 수 없으므로 -1을 출력한다. 이면 아무 나무도 심지 않아도 되므로 답은 이다.
각 공터의 는 주변 칸을 확인하여 구할 수 있다. 는 부터 까지만 가능하므로 각 값의 개수만 세면 정렬도 필요 없다. 시간 복잡도는 각 테스트 케이스마다 이고, 전체 시간 복잡도는 이다. 격자를 저장하는 데 의 메모리를 사용한다.
Solution written by GPT5.6
