[백준] 빗물 14719 자바

두가지 방법이 있는데요, 첫 번째는 구현에 가까운 풀이이구요,(눈물의 풀이입니다.)

두 번째는 좀 더 수학적(?),구조적으로 푼 방법입니다.

 

알면 쉽고 모르면 생각하기 좀 까다로운 문제입니다.

가능하면 두 번째 방법을 추천드립니다. 

 

첫 번째 func() 풀이는 

기준점의 기둥보다 크거나 같은 기둥을 찾아서 그 사이에 모이는 빗물을 더해주는 방법입니다.

기준점보다 크거나 같은 기둥이 없다면 그 중에서 그나마 가장 큰 기둥을 찾아서,

찾은 기둥까지 모인 빗물수 - (기준기둥크기  -  그나마 큰 기둥크기) * (사이에 있는 기둥 수) 를 반환합니다.

(일단은 뒤에 큰 기둥이 있다는 가정하에 무식하게 더하다가 그게 아니니까, 그마나 큰 기둥을 기준으로 그보다 높이 쌓인 빗방울을 없애주는 겁니다.)

 

두 번째 func2()풀이는

기준점의 기둥 왼쪽 오른쪽 으로 뻗어나가서 각각 가장 높은 기둥을 고릅니다

오른쪽 가장 높은기둥과 왼쪽 가장 높은기둥 중에서 제일 낮은 기둥(낮은 만큼만 빗방울이 쌓이니까)을 골라서

그 기둥과 기준점의 기둥의 크기 차이만큼 더해줍니다. (빗방울이 쌓인 높이)

이렇게 끝까지 반복합니다.

 

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

public class 빗물 {

	static int ny, nx;
	static int[] map = new int[501];

	static int find(int start, int high) {

		if (start == nx)
			return start;
		int most = 0;
		int mostidx = 0;

		for (int x = start + 1; x <= nx; x++) {
			int next = map[x];

			if (most <= next) {
				most = next;
				mostidx = x;
			}

			if (next >= high) {
				mostidx = x;
				break;
			}
		}

		return mostidx;

	}

	static int sumf(int start, int end) {
		int sum = 0;
		int gap_idx = end - (start+1);
		int gap_h = map[start] - map[end];
		if (gap_h < 0)
			gap_h = 0;

		for (int x = start + 1; x < end; x++) {
			if(map[start]-map[x] >= 0)
			sum += map[start] - map[x];
		}

		return sum - (gap_idx * gap_h);
	}

	static int func() {
		int sum = 0;

		for (int x = 1; x < nx; x++) {
			int end = find(x, map[x]);
			sum += sumf(x, end);
			x = end-1;
		}

		return sum;
	}
	
	static int func2() {
		int sum =0;
		
		for(int x=1; x<=nx; x++) {
			int lmax = 0;
			int rmax = 0;
			for(int lx = x-1; lx>=1; lx--) lmax = Math.max(lmax, map[lx]);
			for(int rx = x+1; rx<= nx; rx++) rmax = Math.max(rmax, map[rx]);
			
			if(Math.min(lmax, rmax)-map[x] <= 0)
				continue;
			else
				sum += Math.min(lmax, rmax)-map[x];
		}
		
		return sum;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		ny = Integer.parseInt(st.nextToken());
		nx = Integer.parseInt(st.nextToken());

		st = new StringTokenizer(br.readLine());
		for (int x = 1; x <= nx; x++) {
			int y = Integer.parseInt(st.nextToken());

			for (int q = 0; q < y; q++) {
				map[x] = y;
			}
		}

//		System.out.println(func());
		System.out.println(func2());

	}

}