[Algorithm] 🏠울타리 잘라내기

0. 문제

너비가 같고 높이가 다른 판자들이 붙어서 울타리를 구성하고 있을 때, 울타리에서 잘라 가장 큰 직사각형을 만들어라

입력
테스트 케이스(C)
나무 판자의 숫자
나무 판자의 각 높이

출력
가장 큰 직사각형의 넓이

1. 문제 간단 해석

붙어있는 판자에서 자를 수 있는 가장 큰 직사각형의 넓이를 구해라

2. 아이디어

💡 총 3가지 경우가 가능함
1) 반절을 잘랐을 때 왼쪽 부분에서의 직사각형이 가장 클 때
2) 반절을 잘랐을 때 오른쪽 부분에서의 직사각형이 가장 클 때
3) 중간부터 시작해서 높이가 높은 쪽으로 넓혀나갔을 때의 직사각형이 가장 클 때

1,2 는 분할정복을 통해서
3은 오른쪽 왼쪽을 비교해서 높이가 넓은쪽으로 계속해서 직사각형의 넓이를 넓혀가는 코드를 통해서 해결할 수 있음

3. 핵심 풀이

1) 분할정복

int ret = Math.max(solve(left,mid), solve(mid+1,right));

2) 3의 경우

while(left < low || high < right) {
			if(high < right && (low == left || arr[low-1] < arr[high+1])) {
				++high;
				height = Math.min(height, arr[high]);
			} else {
				--low;
				height = Math.min(height, arr[low]);
			}
			
			ret = Math.max(ret, height*(high-low+1));
}

4. 코드

import java.util.Scanner;

public class Fence {
	static int n;
	static int arr[];
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		
		int C = sc.nextInt();
		
		for(int i=0; i<C; i++) {
			n = sc.nextInt();
			arr = new int[n];
			
			for(int j=0; j<n; j++) {
				arr[j] = sc.nextInt();
			}
			
			System.out.println(solve(0,n-1));
		}
	}
	
	static int solve(int left, int right) {
		if(left == right) return arr[left];
		
		int mid = (left+right)/2;
		
		int ret = Math.max(solve(left,mid), solve(mid+1,right));
		
		int low = mid, high = mid+1;
		int height = Math.min(arr[low], arr[high]);
		
		ret = Math.max(ret, height*2);
		
		while(left < low || high < right) {
			if(high < right && (low == left || arr[low-1] < arr[high+1])) {
				++high;
				height = Math.min(height, arr[high]);
			} else {
				--low;
				height = Math.min(height, arr[low]);
			}
			
			ret = Math.max(ret, height*(high-low+1));
		}
		
		return ret;
	}

}

5. 결과

성공~