NM과 K (2)

시간 제한2초메모리 제한512 MB

요약
N×M 격자에서 서로 인접하지 않은 K개의 칸을 골라 값의 합이 최대가 되도록 한다.
난이도

어려움10점 중 8점

유형
동적 계획법, 비트 연산, 완전 탐색, 구현
정답자
아직 제출이 없습니다

문제

크기가 N×M인 격자판의 각 칸에 정수가 하나씩 들어있다. 이 격자판에서 칸 K개를 선택하고, 선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 구하려고 한다. 단, 선택한 두 칸이 인접하면 안 된다. r행 c열에 있는 칸을 (r, c)라고 할 때, (r-1, c), (r+1, c), (r, c-1), (r, c+1)에 있는 칸이 인접한 칸이다.

입력

첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 N개의 줄에 격자판에 들어있는 수가 주어진다.

출력

선택한 칸에 들어있는 수를 모두 더한 값의 최댓값을 출력한다.

제한

  • 1 ≤ N, M ≤ 10
  • 1 ≤ K ≤ min(50, N×M)
  • 격자판에 들어있는 수는 -10,000보다 크거나 같고, 10,000보다 작거나 같은 정수이다.
  • 항상 K개의 칸을 선택할 수 있는 경우만 입력으로 주어진다.

예제4

  1. 예제 1

    입력
    1 1 1
1
    예상 출력
    1

  2. 예제 2

    입력
    2 2 2
1 2
3 4
    예상 출력
    5

  3. 예제 3

    입력
    2 2 2
5 4
4 5
    예상 출력
    10

  4. 예제 4

    입력
    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