Divide and Conquer, 울타리 잘라내기 문제(FENCE)

문제출처: Algospot FENCE 문제.

 

https://www.algospot.com/judge/problem/read/FENCE

 

문제

너비가 같은 N개의 나무 판자를 붙여 세운 울타리가 있습니다. 시간이 지남에 따라 판자들이 부러지거나 망가져 높이가 다 달라진 관계로 울타리를 통째로 교체하기로 했습니다. 이 때 버리는 울타리의 일부를 직사각형으로 잘라내 재활용하고 싶습니다. 그림 (b)는 (a)의 울타리에서 잘라낼 수 있는 많은 직사각형 중 가장 넓은 직사각형을 보여줍니다. 울타리를 구성하는 각 판자의 높이가 주어질 때, 잘라낼 수 있는 직사각형의 최대 크기를 계산하는 프로그램을 작성하세요. 단 (c)처럼 직사각형을 비스듬히 잘라낼 수는 없습니다.

판자의 너비는 모두 1이라고 가정합니다.

입력

첫 줄에 테스트 케이스의 개수 C (C≤50)가 주어집니다. 각 테스트 케이스의 첫 줄에는 판자의 수 N (1≤N≤20000)이 주어집니다. 그 다음 줄에는 N개의 정수로 왼쪽부터 각 판자의 높이가 순서대로 주어집니다. 높이는 모두 10,000 이하의 음이 아닌 정수입니다.

출력

각 테스트 케이스당 정수 하나를 한 줄에 출력합니다. 이 정수는 주어진 울타리에서 잘라낼 수 있는 최대 직사각형의 크기를 나타내야 합니다.

 

아이디어: 분할정복

책에서 제공한 방법대로, 절반을 나누고 각각의 부분에서 최대 넓이를 구하고 가운데 부분에 걸치는 영역에서 좌우로 확장해나가며 넓이를 넓혀가는 방법으로 3가지 넓이를 구하고, 그 3가지 넓이 중에 가장 큰 넓이를 계산하는 과정으로 구현. 

 

어려웠던 부분과 해결방안

가운데를 포함하는 영역의 넓이를 구하는 부분이 제일 어려웠는데, 이것은 lo = mid, hi = mid+1로 초기화하고 lo와 hi를 조건에 따라 1씩 좌우로 이동시키는 방법으로 해결했다.

lo는 left까지 확장하고, hi는 결국 right까지 확장해야한다.

확장할 때에 한칸씩 이동하는데, 왼쪽 오른쪽 중에 높이가 높은 방향으로 이동한다.

만약 최초 높이가 7인 사각형 2개로 시작했을때, 왼쪽으로 이동했을 때에 높이가 2이고 오른쪽으로 이동했을 때에 높이가 5인데, 왼쪽으로 먼저 이동했을 경우,

총 max넓이는 2만큼 증가해서 2*3 = 6이 되고 max는 최초의 넓이인 14이다.  

그리고 나서 오른쪽으로 이동하면 높이가 2에서 더 높아질수가 없어서 2*4 = 8이라서 max는 여전히 14이다.

 

하지만, 오른쪽이 더 높다는 것을 알아차리고 오른쪽으로 먼저 이동했을 경우,

min(높이)는 5가 되어 5*3 = 15의 넓이를 얻고 max(14, 15) = 15 라서 15가 새로운 max가 된다.

그리고 나서 왼쪽으로 이동하면 넓이는 다시 높이 2의 제한에 걸려 감소하지만 max는 15가 된다.

 

이 2가지 경우에서 알 수 있듯, 이동시에 높이가 더 높은쪽으로 이동하지 않으면 max를 정확하게 알 수 없다.

 

다음은 코드이다.

 

#입력 받는 부분
import sys
C = int(sys.stdin.readline())
L_list = []
H_list = []
for i in range(C):
    L_list.append(int(sys.stdin.readline()))
    temp = list(map(int, sys.stdin.readline().split()))
    H_list.append(temp)

# L_list[ 0 ~ C-1 ]
# i = o ~ C-1
# H_list[i][ 0 ~ L_list[i] ]

print('\n')
for i in range(C):
    print(L_list[i])
    print(H_list[i])

# 직사각형의 넓이는 (r-l+1)*min(h[i]) h[i]는 r과 l사이의 막대들의 넓이.
# 그 넓이 중 가장 짧은 것과 밑변의 길이를 곱한 값이 직사각형의 넓이.

# 높이 배열과 시작 인덱스와 끝 인덱스가 주어지면 넓이를 구하는 함수.
def area(which_case, start, end):
    return min(H_list[which_case][end:start+1])*(end - start + 1)

# 3가지 부분의 최대 직사각형의 넓이를 출력
# 기저 케이스: 1칸만 남는 경우.
def solve(which_case, left, right):
    if left == right:
        return H_list[which_case][left]
    # [left, mid]와 [mid+1, right]로 2개로 나눈다.
    mid = int((left + right)/2)
    ret = max(solve(which_case, left, mid), solve(which_case, mid+1, right))

    # 가운데 부분을 포함하는 사각형의 넓이를 계산.
    lo = mid
    hi = mid+1
    height = min(H_list[which_case][lo], H_list[which_case][hi])
    ret = max(ret, height*2) # height의 높이를 가지고 밑변이 2인 사각형과 앞서 구한 2개의 사각형 중 큰 것을 구한다.
    while( left < lo or hi < right ):
        # 높이가 더 높은 쪽으로 확장한다.
        if hi < right and ((lo == left) or (H_list[which_case][lo-1] < H_list[which_case][hi+1])):
            hi += 1 # 오른쪽이 더 놓은 경우라서 오른쪽으로 한 칸 이동한다.
            height = min(height, H_list[which_case][hi]) # 둘 중 큰 높이.
        else:
            lo -= 1
            height = min(height, H_list[which_case][lo])
        ret = max(ret, height * (hi - lo + 1))
    return ret

for i in range(C):
    print(i+1,'번째 입력에 대한 출력:',solve(i,0,L_list[i]-1))