답안

import java.util.Arraist;
import java.util.Collections;

public class Main {    
	public static void main(String[] args) {
		int h = 7;
		int w = 6;
		int[] column = {6, 5, 7, 3, 4, 2};
		
		int[] answer = solution(h, w, column);
		System.out.println(answer[0] + " " + answer[1]);
	}

	public static int[] solution(int h, int w, int[] column) {		
		int[] dp_l = new int[w];
		int max_l = -1;
		for (int i = 0; i < w; i++) {
			max_l = Math.max(column[i], max_l);
			dp_l[i] = max_l;
		}
		
		int[] dp_r = new int[w];
		int max_r = -1;
		for (int i = w - 1; i >= 0; i--) {
			max_r = Math.max(column[i], max_r);
			dp_r[i] = max_r;
		}
		
		ArrayList<Integer> list = new ArrayList<Integer>();
		int sum = 0;
		for (int i = 0; i < w; i++) {
			int differ = Math.min(dp_l[i], dp_r[i]);
			list.add(differ - column[i]);
			sum += differ - column[i];
		}
		
		return new int[] {sum, Collections.max(list)};
	}
}

1. 문제 파악

1. 기둥과 기둥 사이에 시멘트를 부울 수 있지만, 두 기둥 중 작은 기둥의 높이까지만 부을 수 있다.

2. 최대한 높이 차가 적도록 하기 위해서는 기준이 되는 두 기둥을 잘 선정해야 한다.

3. 현재 위치에서 오른쪽에서 가장 큰 높이, 왼쪽에서 가장 큰 높이를 구해 그 중 작은 값을 기준으로 해서 현재 값을 빼주는 방식을 사용하면 부을 수 있는 시멘트 양을 알아낼 수 있다.

4. 정방향과 역방향으로 반복문을 진행해 각각의 최댓값을 저장할 수 있도록 배열을 선언해야 한다.

2. 풀이

1. 왼쪽에서부터 끝까지 반복문을 돌면서 기둥의 최댓값과 현재 기둥의 높이를 비교한 뒤, 더 큰 값을 dp_l 배열에 저장합니다. 이때, 현재 기둥의 높이가 더 크다면 max_i 값을 갱신해 줍니다.

int[] dp_l = new int[w];
int max_l = -1;
for (int i = 0; i < w; i++) {
		max_l = Math.max(column[i], max_l);
		dp_l[i] = max_l;
}

 

2. 마찬가지로 오른쪽에서부터 왼쪽까지 반복문을 돌면서 1번과 같은 과정을 거칩니다.

int[] dp_r = new int[w];
int max_r = -1;
for (int i = w - 1; i >= 0; i--) {
		max_r = Math.max(column[i], max_r);
		dp_r[i] = max_r;
}

 

3. 가장 높게 쌓인 시멘트의 높이를 구해야 하기 때문에 ArrayList를 선언합니다.

ArrayList<Integer> list = new ArrayList<Integer>();

 

4. 기둥 사이에 쌓을 수 있는 시멘트의 양은 두 기둥 중 작은 기둥의 높이까지만 부을 수 있기 때문에 dp_l과 dp_r 두 가지 값 중 작은 값을 고릅니다.

int differ = Math.min(dp_l[i], dp_r[i]);

 

5. 4번에서 구한 값과 현재 기둥의 차이를 구해 시멘트의 양을 구하고, 이 값을 sum에 더해 시멘트의 총량을 알아냅니다.

list.add(differ - column[i]);
sum += differ - column[i];