BOJ - 12846 ) 무서운 아르바이트

 

---

 

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

12846번: 무서운 아르바이트

---

연속한 수열에서 가장 최솟값을 기준으로 얻을 수 있는 총합의 가장 큰 값을 고르는 문제이다.

 

문제상황을 잘 읽어보면,

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

6549번: 히스토그램에서 가장 큰 직사각형

 

이 문제와 완전한 동치임을 알 수 있다. 즉 가장 큰 직사각형의 넓이를 구하기위해,

밑변을 세그먼트트리의인덱스로 설정하고 해당 수열에서 가장 낮은 ( 높이를 결정하는 ) 값의 인덱스를

세그먼트 트리에 넣어두었다.

 

또한 재귀함수를 통하여, 밑변의 길이가 1인 직사각형까지 모두 탐색한다.

즉, 연속된 날짜에 아르바이트를 하더라도, 가장 낮은임금을 기준으로 급여를 받기 때문에,

가장 낮은 임금의 인덱스를 저장하며 직사각형처럼 풀어준다.

 

재귀의 다음 STEP으로는 현재 인덱스의 좌우를 변수로 주어탐색한다.

---

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

public class 무서운아르바이트 {
	
	public static int n;
	public static int arr[];
	public static int seg[];
	public static long answer = -1;
	public static int out = 987654321;
	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		n = Integer.parseInt(st.nextToken());
		st = new StringTokenizer(br.readLine());
		arr = new int[n]; seg=new int[4*n];
		for(int i=0;i<n;++i) {arr[i]=Integer.parseInt(st.nextToken());}
		seginit(1,0,n-1);
		dfs(0,n-1);
		System.out.println(answer);
	}
	
	private static void dfs(int s, int e) {
		if(e<s)return;
		if(s==e) {
			long res = arr[e];
			answer = answer > res ? answer : res;
			return ;
		}
		int index = findmin(1,0,n-1,s,e);
		long res = (long)(e-(s-1)) * (long)arr[index];
		answer = answer > res ? answer : res;
		dfs(s,index-1);
		dfs(index+1,e);
	}

	private static int seginit(int now, int s, int e) {
		// 구간의 가장작은 높이의 인덱스를 저장
		if(s==e) {return seg[now] = s;}
		else {
			int l = seginit(now*2,s,(s+e)>>1);
			int r = seginit(now*2+1,((s+e)>>1)+1,e);
			return (seg[now] = (arr[l]>arr[r]?r:l));		
		}
	}
	
	private static int findmin(int node, int l, int r , int s  , int e) {
		if(r < s || e < l) return out;
		else if( s <= l && r<= e) return seg[node];
		int rr = findmin(2*node, l, (r+l)>>1, s, e);
		int ll = findmin(2*node+1, ((r+l)>>1)+1, r, s, e);
		if(rr==out && ll!= out) return ll;
		if(rr!=out && ll== out) return rr;
		// 둘다 out인경우가? 존재할수 없다
		return arr[rr] > arr[ll] ? ll : rr ;
	}
}

---