[BOJ] 백준 12846번 무서운 아르바이트 (Java)

#12846 무서운 아르바이트

난이도 : 플레 5

유형 : 세그먼트 트리 / 분할정복

12846번: 무서운 아르바이트

▸ 문제

성화는 악독하기로 유명한 편의점 사장이다. 그의 편의점에는 특이한 임금 체계를 가지고 있다.

• 각 날마다 일의 차이때문에 일마다 급여가 정해져 있다.
• 돈은 당일에 주지 않고 퇴직을 할 때 한번에 준다.
• 성화는 욕심쟁이라서 해당 일을 한 동안 중 가장 일급이 작을 때를 기준으로 급여를 지급한다.
• 일급이 다른 것을 들키지 않기 위하여 한번이라도 퇴직한 자를 다시 취직 시키지 않는다. (만약 취직을 한다면, 일을 시작 한 날부터 끝날 때까지 하루도 빠지면 안 된다.)

준수는 n+1일 후에 001에 월세를 내야 해서 성화가 사장으로 있는 편의점에 취직하려 한다. 다행히 주변 퇴직자들의 얘기로 급여에 관련해 파악했다. 또한 퇴직자들의 급여 통계를 통해 당장 n일 후까지 일급 정보를 알아냈다. 최대로 많이 일했을 때가 최대 이익이 아닐 수 있다.

어제까지 과제를 제출하고 지금도 001에서 자고 있는 준수를 위해 코딩 잘하는 여러분이 일을 해서 벌 수 있는 최대 이익을 준수에게 알려주도록 하자.

▸ 입력

일을 할 수 있는 날의 수 (0 < n ≤ 100000) 가 주어진다.

그 다음 줄 에는 1일부터 n일 까지 일급 Ti 가 순서대로 주어진다. (0 < Ti ≤ 1,000,000)

▸ 출력

준수가 일을 해서 벌 수 있는 최대 이익을 출력한다.

 

문제 풀이  

히스토그램에서 가장 큰 직사각형을 구하는 문제랑 동일하다.

 

히스토그램에서 가장 큰 직사각형 구하기

 

n은 최대 10만으로 브루트포스하게 찾으면 10만*10만으로 시간초과가 발생한다. 그래서 세그먼트 트리를 활용하여 log 시간복잡도로 줄여줘야 한다. 그리고 [1, n]구간에서 가장 큰 넓이를 구해야하므로 이또한 선형탐색이 아닌 분할정복을 활용해줘야 한다. 

• 따라서 세그먼트 트리를 이용한 [a, b]의 최소 높이 구하기 + [a, b] 구간 분할정복으로 가장 큰 영역구하기 문제라고 볼 수 있다.

 

세그먼트 트리를 이용한 [l, r] 최소 높이 구하기

먼저 인덱스 트리를 초기화 해준다. 인덱스로 저장하는 이유는 분할정복할 때 구간(인덱스)로 나눠야하기 때문이다. 

인덱스 트리

 

[l, r] 구간 분할정복으로 가장 큰 영역 구하기

getMax(l, r)

1. m: [l, r] 구간에서 가장 작은 크기를 가지는 인덱스를 구한다.
2. area: l~r 동안 일하면서 받을 수 있는 월급의 총액을 구한다. 
3. 최솟값 m을 기준으로 왼쪽, 오른쪽 분할하여 재귀 탐색한다.
   1. l <= m-1,  getMax(l, m-1)
   2. m+1 <= r, getMax(m+1, r)
   3. 탐색 결과, area 최댓값을 갱신해준다.
4. 모든 분할정복이 끝나고 가장 큰 area 값을 반환한다.

 

예제로 시뮬레이션을 돌려보면 다음과 같다.

getMax(1, 5)

• m = 5, area = (5-1+1)*arr[5] = 50
• l  <= m-1 → 1 <= 4,  getMax(1, 4)
• m+1 < r, 6 < 5 

getMax(1, 5)

 

getMax(1, 4)

• m = 1, area = (4-1+1)*arr[1] = 40
• l <= m-1 → 1 <= 0
• m+1 < r → 2 < 4, getMax(2,4)

 

getMax(1, 4)

 

getMax(2, 4)

• m = 2, area = (4-2+1)*arr[2] = 60

 

이런식으로 분할정복을 하여 최댓값을 구해 출력해주면 된다. 

 

풀이 코드 

import java.io.*;
import java.util.*;

public class Main {
	static int n;
	static int[] arr, tree;
	public static void main(String[] args) throws  IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		 n = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		arr = new int[n+1];
		for(int i=1; i<=n; i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		tree = new int[n*4];
		
		init(1, n, 1);
		System.out.println(getMax(1,n));
	}
	
	static void init(int s, int e, int node) {
		if(s == e) {
			tree[node] = s;
			return;
		}
		
		int mid = (s+e)/2;
		init(s, mid, node*2);
		init(mid+1, e, node*2+1);
		if(arr[tree[node*2]] < arr[tree[node*2+1]]) {
			tree[node] = tree[node*2];
		}else {
			tree[node] = tree[node*2+1];
		}
	}
	
	static int query(int s, int e, int node, int l, int r) {
		if(r < s || e < l) return -1;
		if(l <= s && e <= r) {
			return tree[node];
		}
		
		int mid = (s+e)/2;
		int lNode = query(s, mid, node*2, l, r);
		int rNode = query(mid+1, e, node*2+1, l, r);
		
		if(lNode == -1) {
			return rNode;
		}else if(rNode == -1) {
			return lNode;
		}
		
		if(arr[lNode] <= arr[rNode]) {
			return lNode;
		}else return rNode;
		
	}
	
	static long getMax(int l, int r) {
		int m = query(1, n, 1, l, r);
		
		long area = (long)(r-l+1)*arr[m];
		if(l <= m-1) {
			long tmp = getMax(l, m-1);
			area = Math.max(area, tmp);
		}
		
		if(m+1 <= r) {
			long tmp = getMax(m+1, r);
			area = Math.max(area, tmp);
			
		}
		return area;
	}

}