HomeAboutMeBlogGuest
© 2025 Sejin Cha. All rights reserved.
Built with Next.js, deployed on Vercel
🗝️
보너스 문제 :: 공사/
🔎
답안
🔎

답안

1. 문제 파악2. 풀이

1. 문제 파악

  1. 기둥과 기둥 사이에 시멘트를 부울 수 있지만, 두 기둥 중 작은 기둥의 높이까지만 부을 수 있다.
  1. 최대한 높이 차가 적도록 하기 위해서는 기준이 되는 두 기둥을 잘 선정해야 한다.
  1. 현재 위치에서 오른쪽에서 가장 큰 높이, 왼쪽에서 가장 큰 높이를 구해 그 중 작은 값을 기준으로 해서 현재 값을 빼주는 방식을 사용하면 부을 수 있는 시멘트 양을 알아낼 수 있다.
  1. 정방향과 역방향으로 반복문을 진행해 각각의 최댓값을 저장할 수 있도록 배열을 선언해야 한다.

2. 풀이

  1. 왼쪽에서부터 끝까지 반복문을 돌면서 기둥의 최댓값과 현재 기둥의 높이를 비교한 뒤, 더 큰 값을 dp_l 배열에 저장합니다. 이때, 현재 기둥의 높이가 더 크다면 max_i 값을 갱신해 줍니다.
      2.  
  1. 마찬가지로 오른쪽에서부터 왼쪽까지 반복문을 돌면서 1번과 같은 과정을 거칩니다.
      2.  
  1. 가장 높게 쌓인 시멘트의 높이를 구해야 하기 때문에 ArrayList를 선언합니다.
      2.  
  1. 기둥 사이에 쌓을 수 있는 시멘트의 양은 두 기둥 중 작은 기둥의 높이까지만 부을 수 있기 때문에 dp_l과 dp_r 두 가지 값 중 작은 값을 고릅니다.
      2.  
  1. 4번에서 구한 값과 현재 기둥의 차이를 구해 시멘트의 양을 구하고, 이 값을 sum에 더해 시멘트의 총량을 알아냅니다.
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)};
	}
}
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 differ = Math.min(dp_l[i], dp_r[i]);
list.add(differ - column[i]);
sum += differ - column[i];