퍼즐놀이를 좋아하는 철기는 도미노를 가지고 노는 것을 좋아한다. 철기는 N×M크기의 보드에 수들을 적어놓고, 그 위에 2×1, 혹은 1×2의 도미노를 덮으려 한다.

이 때, 절댓값(각 도미노가 덮는 두 수의 차이)의 총 합이 최대가 되도록 하려 한다. 하나의 칸에는 한 개의 도미노만 올려놓을 수 있으며, 도미노가 올려져있지 않은 칸이 생길 수도 있다. 뿐만 아니라, 두 수의 차이가 T보다 큰 경우에는 두 수 위에 도미노를 덮어놓을 수 없다.

아래와 같이 보드가 있다고 하자.

1 1

10 10

예를 들어 위의 2×2배열(T=9)을 두 가지 방법으로 덮을 수 있는데,

(1, 1), (10, 10)을 덮은 경우에는 덮인 수들의 차이의 총 합이 0(|1-1| + |10-10|)이 되지만, (1, 10), (1, 10)으로 덮으면 18(|1-10|+|1-10|)이 된다. 그리고 이 방법이 최적해이다.

#2215 upload - done - how_to_reg -

도미노 놀이 timer 2s memory - MB

#2215

도미노 놀이 2s - MB