다이아몬드 광산을 운영하는 반딧불은 지난 jungol 왕국과의 거래로 많은 수익을 얻었다.

또한 지난 계약을 잘 이해한 덕분에 N * N 넓이에 대한 새로운 채굴 허가를 얻었다.

나름 좋은 조건에 채굴계약을 채결하였는데 계약서에 따르면 다음 세 가지를 꼭 준수해야 했다.

광산을 정방형의 그리드 모양으로 나누었을 때,

1. 각 행마다 연속한 K구간을 채굴한다. 2. 채굴한 곳들을 통로로 볼 때 채굴영역의 왼쪽 바깥과 오른쪽 바깥 사이에 경로가 생기지 않도록 해야 한다. 3. 채굴한 곳들을 통로로 볼 때 채굴영역의 위쪽 바깥과 아래쪽 바깥 사이에 경로가 생기지 않도록 해야 한다.

N=5이고 K=2인 경우를 예로 들어 살펴보자면 아래 그림들 중에 입력 예를 설명하고 있는 그림1만 가능한 경우가 된다.

그림2는 조건1를 어겼으며 그림3은 조건2를 어긴 경우이다. 그림4는 조건3을 어긴 경우이다.

사업가답게 반딧불은 N * N구간을 단위크기로 나누어 각 격자 크기의 영역에 대한 상품성을 조사한 가격표를 만들었다. 이제 채굴을 하려고 한다. 반딧불은 최대 얼마의 수익을 얻을 수 있을까?

다이아몬드 광산 timer 1000초 memory 128MB

다이아몬드 광산 1000초 128MB