[문제][알고스팟] 울타리 잘라내기

문제 정보

• • 문제 ID
  • 시간 제한
  • 메모리 제한
  • 제출 횟수
  • 정답 횟수 (비율)
• • FENCE
  • 3000ms
  • 131072kb
  • 10450
  • 3212 (30%)
• • 출제자
  • 출처
  • 분류
• • JongMan
  • 알고리즘 문제 해결 전략
  • 보기

문제

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

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

입력

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

출력

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

예제 입력

3
7
7 1 5 9 6 7 3
7
1 4 4 4 4 1 1
4
1 8 2 2

예제 출력

20
16
8

그냥 빨리 풀어버렸다.

항상 느끼는건 내가 푸는 것에 대한 정당성 증명이 완벽하게 와닿진 않는다. 귀류법으로 증명하면 논리적으로 참이라는건 이해가 가지만 그렇다고 처음 본 문제에서 가설을 세우기가 여전히 어렵다. 다들 완벽하게 알고 정당성까지 입증하고 푸는걸까? 아직 모르겠다.

package apss;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;

public class Fence {
	
	public static int N;	// 1<= N <= 20000
	public static int height[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		// TODO Auto-generated method stub
		
		System.setIn(new FileInputStream("D://sample_input.txt"));
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int T = Integer.parseInt(br.readLine());
		for(int testCase=1; testCase<=T; testCase++) {
			N = Integer.parseInt(br.readLine().trim());
			
			StringTokenizer st = new StringTokenizer(br.readLine());
			
			height = new int[N];
			for(int i=0; i<N; i++) {
				height[i] = Integer.parseInt(st.nextToken());
			}
			
			int result = getMaxArea(0,N-1);
			
			bw.flush();
			bw.write(result+"\n");
		}
		bw.close();

	}
	
	public static int getMaxArea(int left, int right) {
						
		if(left == right) {
			return height[left];
		}
		
		int mid = (right + left)/2;
		int ret = Math.max(getMaxArea(left,mid), getMaxArea(mid+1,right));
		
		int lo = mid, hi = mid+1;
		int midHeight = Math.min(height[lo], height[hi]);
		
		ret = Math.max(ret, midHeight*2);
		
		while(left < lo || hi < right) {
			if(hi < right && (lo == left || height[lo-1] < height[hi+1])) {
				hi++;
				midHeight  = Math.min(midHeight, height[hi]);
			}else {
				lo--;
				midHeight = Math.min(midHeight, height[lo]);
			}
			ret = Math.max(ret, midHeight * (hi-lo+1));
		}
		
		return ret;	
		
	}

}