정올_1214 히스토그램(자바) / 자료구조

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.jungol;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class jungol_1214 {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		long[] H = new long[N+2];
		
		for (int i = 1; i < N+1; i++) {
			H[i]=Integer.parseInt(st.nextToken());
		}
		Long R, L,ans=(long) 0;
		for (int i = 1; i < N+1; i++) {
			R=(long) 0;
			L=(long) 0;
			//오른쪽 비교
			for (int j = i+1; j < H.length; j++) {
				if(H[i]>H[j]) {
					R=H[i] *(j-i);
					break;
				}
			}
			//왼쪽
			for (int j = i-1; j > 0; j--) {
				if(H[i]>H[j]) {
					 L=H[i]*(i-1-j);
					 break;
				}
			}
			ans = Math.max(ans, R+L);
		}
		System.out.println(ans);
	}
}

 

- 히스토그램은 가장 넓은 사각형의 크기를 구하는 문제입니다.

 

- 이 문제에 대한 해결 아이디어는 칸을 오른쪽으로 한칸씩 옮겨 가면서 다 확인하는 방법입니다.

 

- 이동했을때 그 칸에 해당하는 칸보다 좌 우 의 칸들이 더 작으면 크기를 더해줍니다.

 

- 오른쪽, 왼쪽의 크기를 더했을 때, 맥스 값을 구해주면 됩니다.