뉴비의 PS 낙서장

https://www.acmicpc.net/problem/4011 4011번: 기름 파기 첫 번째 줄에는 세 개의 정수 M, N, K가 주어지는데, M과 N은 각각 직사각형 격자의 행과 열 개수이고 K는 한 사업자가 입찰에 응할 수 있는 정사각형 구역 한 변의 크기이다. 다음 M개의 줄에는 각 www.acmicpc.net 구역을 최대 3개만 팔 수 있기 때문에 여러가지 경우를 구상해 볼 수 있다. 총 6가지 경우가 있다. 왼쪽 위에서 부터 시작하는 DP, 오른쪽 위에서 부터 시작하는 DP, 왼쪽 아래에서 부터 시작하는 DP, 오른쪽 아래에서 부터 시작하는 DP테이블을 만든다. DP테이블의 정의는 \(dp[i][j]\) : 시작점부터 \((i,j\))까지 의 영역에서 기름을 파낼 한 구간을 구할 때 최대 ..