전형적인 다이나믹 문제이다.T[c][r][k] 를 1~c열까지 사용하여 c번째 열에서는 i~N(r <= i <= N+1) 행을 사용할 때 k 라는 합을 만들 수 있는지의 여부로 정의한다. 이와 같이 정의하면 다음과 같이 점화식을 세울 수 있다.
- T[c][r][k] = T[c][r+1][k]|T[c-1][r][k-S(c,r)]
- S(c,r)= c열에서 r~N행까지의 논의 수확량의 합
이를 기본으로 하여 T[N][0][k] (0<=k<=Max_수확량)을 차례대로 검색하면서 논의 수확량을 최소화할 수 있는 것을 찾아주면 된다.
시간 복잡도와 공간복잡도는 O(N^4*M)이 된다. 문제의 특성상 다양한 휴리스틱으로 해결이 가능할 수 있다.