N 열로 구성된 조각이 아래 그림과 같이 주어진다.

위 예시 그림에서는 N = 6 이고, 각 열의 높이는 [ 2, 4, 3, 2, 1, 3 ] 이다.

정올이는 "하나의 연결된 조각" 을 이 위에 붙여서 직사각형을 만드려고 한다.

예를 들어, 아래와 같이 할 수 있다.

이 때 정올이가 사용한 녹색 조각의 크기는 27 이다. ( 조각의 크기는, 그 조각에 포함된 단위 칸들의 개수다. )

아래는 불가능한 경우다.

위 그림이 불가능한 이유는, 녹색 조각이 하나로 연결되어 있지 않기 때문이다.

즉, 조건을 만족하며 직사각형을 만드는 가장 작은 조각은 아래 그림과 같다.

이 조각의 크기는 15 이고, 이 값이 최소다.

직사각형을 만드는 가장 작은 조각의 크기를 찾는 프로그램을 작성하자.

딱 맞는 조각 timer 2s memory 512MB

딱 맞는 조각 2s 512MB