시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 292 | 95 | 78 | 41.053% |
크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택할 것이고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안된다. r행 c열에 있는 칸을 (r, c)라고 했을 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.
선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.
1 1 1 1
1
2 2 2 1 2 3 4
5
2 2 2 5 4 4 5
10
5 5 3 1 9 8 -2 0 -1 9 8 -3 0 -5 1 9 -1 0 0 0 0 9 8 9 9 9 0 0
27