[14727] 퍼즐 자르기 - Java[자바]

 

 

| 문제 링크

 

 

https://www.acmicpc.net/problem/14727

14727번: 퍼즐 자르기

 

 

 

 

 

---

 

 

 

 

 

| 문제

 

1. 히스토그램을 구성하는 N개의 바의 높이(Hi)가 주어집니다. (1 ≤ Hi ≤ 1,000,000)
2. 퍼즐을 잘랐을 때 구할 수 있는 직사각형의 최대 부피를 구하시오.

 

 

 

 

---

 

 

 

 

| 풀이

 

1. 자식들이 포함한 리프 노드(히스토그램)들 중 가장 높이가 낮은 리프 노드의 인덱스를 가지는 세그먼트 트리를 만듭니다.
2. 해당 인덱스에 해당하는 히스토그램 높이와 target 리프 노드의 범위 +1을 곱한 값이 면적이됩니다.
3. 2번에서 구한 인덱스를 기준으로 왼쪽과 오른쪽을 나누어(idx의 범위가 벗어나지 않는다면), 1번에서 target 리프 노드에 해당하는 리프 노드들 중 가장 높이가 낮은 리프 노드의 인덱스를 구해 2번 계산을 반복해줍니다.
4. 2번과 3번에서 구한 면적을 중 가장 큰 값을 출력합니다.

 

 

하위 코드의 주석을 보시고 이해에 도움이 되기를 바랍니다.

 

 

 

 

 

---

 

 

 

 

 

| 코드

 

import java.io.*;

public class Main {
	
	public static int[] tree, arr;
	public static int n;

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));		
		
		n = Integer.parseInt(br.readLine());
		
		arr = new int[n+1];
		
		for(int i = 1; i<=n; i++)
			arr[i] = Integer.parseInt(br.readLine());
		
		int k = (int) Math.ceil(Math.log(n)/Math.log(2)) + 1;
		int size = (int) Math.pow(2, k);
		
		tree = new int[size];
		
		init(1,n,1);
		bw.write(String.valueOf(getMax(1,n)));
		br.close();
		bw.close();
		
	}
	
	/*
	 * 자식들 중 높이가 낮은 인덱스를 출력하는 세그먼트 트리
	 * s: 탐색하고자 하는 리프 노드의 시작
	 * e: 탐색하고자 하는 리프 노드의 끝
	 * node: 현재 세그먼트 트리 노드
	 */
	public static int init(int s, int e, int node) {
		//리프 노드에 도달한 경우 해당 리프노드의 인덱스를 기재
		if(s==e)
			return tree[node] = s;
		//완전 이진 트리의 특성을 이용해 mid를 중점으로 왼쪽 자식이 s~mid, 오른쪽 자식이 mid+1~e
		int mid = (s+e) >>> 1;
		
		//왼쪽 자식 중 높이가 가장 낮은 리프 노드와 오른쪽 자식 중 높이가 가장 낮은 리프 노드를 비교해 더 낮은 리프 노드의 인덱스를 리턴
		if(arr[init(s,mid,node*2)]<=arr[init(mid+1,e,node*2+1)])
			return tree[node] = tree[node*2];
		else
			return tree[node] = tree[node*2+1];
		
	}
	
	/*
	 * target 범위 중 높이가 가장 낮은 인덱스를 호출
	 * s: 탐색하고자 하는 리프 노드의 시작
	 * e: 탐색하고자 하는 리프 노드의 끝
	 * node: 현재 세그먼트 트리 노드
	 * L: target 리프 노드의 시작
	 * R: target 리프 노드의 끝
	 */
	public static int minIdx(int s, int e, int node, int L, int R) {
		if(e<L || R<s)
			return -1;
		if(L<=s && e<=R)
			return tree[node];
		
		int mid = (s+e) >>> 1;
		
		int left = minIdx(s,mid,node*2,L,R);
		int right = minIdx(mid+1,e,node*2+1,L,R);
		
		if(left == -1)
			left = right;
		if(right == -1)
			right = left;
		
		if(arr[left]<=arr[right])
			return left;
		else
			return right;
	}
	
	/*
	 * 분할 정복 메서드
	 * L: target 리프 노드의 시작
	 * R: target 리프 노드의 끝
	 */
	public static long getMax(int L, int R) {
		//높이가 가장 낮은 히스토그램의 인덱스를 추출
        int idx = minIdx(1,n,1,L,R);
        //면적을 구함
		long space = (long)(R-L+1)*(long)arr[idx];
		
        //인덱스를 기준으로 왼쪽으로 갈 수 있다면 왼쪽 구역을 나누어 재탐색
		if(L<idx) {
			long left = getMax(L,idx-1);
			space = (long) Math.max(space, left);
		}
        //인덱스를 기준으로 오른쪽으로 갈 수 있다면 오른쪽 구역을 나누어 재탐색 
		if(idx<R) {
			long right = getMax(idx+1,R);
			space = (long) Math.max(space, right);
		}
		return space;
	}
	
}