Koi4u 2004 모의고사 3. 종이 자르기

 N×M 크기의 격자로 이루어져 있는 직사각형 종이를 자르려고 한다. (N, M은 홀수) 밑의 <그림 1>의 경우에는 N = 3, M = 5 인 경우이며 그림처럼 맨 가운데 칸을 제외한 모든 격자에 정수가 써져 있다.

가운데 칸을 제외하면, 한번의 가위질로 두 부분으로 종이를 자를 수 있다. 단, 종이를 잘라 생기는 두 직다각형 모양의 종이는 반드시 회전하여 완전히 포갤 수 있어야 한다. 이 경우, 종이를 자르는 방법은 여러 가지가 있을 수 있다.

  <그림 2>의 경우는 위의 규칙에 맞게 종이를 자른 예 중 하나를 나타낸 것이다. 이 경우 직다각형 A와 B는 서로 회전하엿을때 완전히 포개진다.

  이 때, 새로 생긴 직다각형에 써져있는 모든 수를 합한 것을 그 직다각형의 점수라고 한다. (점수는 음수가 될 수도 있다.) 이제 해야 할 일은 두 직다각형의 점수의 차를 가장 크게 하는 것이다.

  <그림 2>처럼 잘랐을 때, 직다각형 A의 점수는 2+1+4+5-5+0+9 = 16이고, 직다각형 B의 점수는 7+5-6+3+2-1+1 = 11이다. 따라서 이 경우 점수의 차는 16-11=5가 된다. (이 경우가 최적해는 아니다)

  프로그램 이름은 CUTRECT.EXE 로 하고, 제한 시간은 5초이다.

입력 파일의 이름은 cutrect.in 으로 한다. 첫 줄에 N과 M이 주어진다. N은 5보다 크지 않은 자연수이며, M은 50 이하의 자연수이다. 둘째 줄부터 N+1번째 줄에는 각각 해당하는 직사각형 종이에 써져있는 M개의 자연수가 들어온다. 직사각형 종이에 써져 있는 모든 수는 -100 이상 100 이하 자연수라고 가정하며, 맨 가운데 칸에는 반드시 0이 들어온다고 가정한다. N과 M은 모두 홀수이다.

출력 파일의 이름은 cutrect.out 으로 한다. 첫 줄에 두 직사각형의 점수의 차의 최대값을 출력한다. 모든 답은 signed 32bit 정수형을 넘지 않는다고 가정한다.

입력(cutrect.in)

출력(cutrect.out)

부분점수는 없다.

저는 휴리스틱(이라고 하나요?? 자세히는 모르겠습니다.)이 뭔지도 모르겠고 사용하는 방법도 몰라서 그냥 단순하게 

모든 가능성을 일일히 최대값과 비교해서 답을 구하는 법 밖에 모릅니다.

그런데 저런 문제들은 모든 가능성을 어떻게 구해야 할 지도 모르겠네요..

직접 손으로 구해보려고 해도 시간이 많이 들어 엄두도 못 내겠구요..

프로그래밍이 너무너무 좋은데 2주일째 이 부분에서 막혀 진행이 안되니 미치겠습니다.