쥐덫
시간 제한1초메모리 제한128 MB
N x N 격자에서 각 행마다 연속된 K개의 칸을 골라 제거하되, 좌우와 상하로 통로가 생기지 않게 하면서 제거량을 최대화하는 문제입니다.
문제
상근이는 집 지하실에서 쥐를 발견했다. 쥐를 매우 싫어하는 상근이는 지하실에 많은 쥐덫을 설치했다.
지하실은 N x N 격자로 나타낼 수 있다. 각 칸에는 그 칸에 설치된 쥐덫의 개수가 적혀 있으며, 모든 칸에는 적어도 1개의 쥐덫이 있다.
정인이도 집 지하실에서 쥐를 발견했다. 하지만 새로 살 수 있는 쥐덫이 없어서, 상근이에게 쥐덫을 빌리려고 한다.
두 사람은 상근이의 지하실에서 일부 쥐덫을 제거해 정인이에게 주기로 했다. 구체적으로는 격자의 각 행마다 연속된 K개의 칸을 하나씩 선택하고, 선택한 칸에 있는 쥐덫을 모두 제거해 정인이에게 준다.
쥐덫을 제거한 뒤에도 쥐가 상근이의 지하실에서 왼쪽 벽에서 오른쪽 벽으로 지나가거나, 위쪽 벽에서 아래쪽 벽으로 지나갈 수 없어야 한다. 쥐는 위, 아래, 왼쪽, 오른쪽 네 방향으로 이동할 수 있고, 쥐덫이 하나도 남아 있지 않은 칸만 지나갈 수 있다.
이 조건을 만족하면서 제거할 수 있는 쥐덫의 최대 개수를 구하라.
입력
첫째 줄에 N과 K가 주어진다. N은 지하실의 크기이고, K는 각 행에서 선택해야 하는 연속된 칸의 개수이다.
2 <= N <= 250, 1 <= K <= N/2
출력
상근이의 지하실에서 제거할 수 있는 쥐덫의 최대 개수를 출력한다.