[BOJ]14719번 : 빗물

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

14719번: 빗물

 

 

알고리즘 분류

• 구현
• 시뮬레이션

 

문제 풀이

 

분류가 구현, 시뮬레이션으로 되어 있어서 탐색 관련인가.. 하는 생각이 들었는데 다른 방법으로도 풀린다.

 

1. 가장 좌측과 우측은 물이 고이지 못한다. (물이 고일 수 있는 범위는 1 <Index < W-1)

2. 현재 위치에서 좌측에서 가장 큰 블록과 우측에 가장 큰 블록을 구한다.

3. 좌측Max값과 우측 Max 값을 비교하여 Min 값에서 현재 위치의 블록 길이를 빼준다

(단, 계산 값이 음수가 나올 수 있으므로 처리해줘야 한다.)

 

import java.util.*;

public class Main {
    
    public static void main(String[] args) 
    {
        Scanner sc = new Scanner(System.in);
        
        int H = sc.nextInt();
        int W = sc.nextInt();
 
        int leftMax = 0;
        int cur     = 0;
        int rightMax= 0;        
        int answer  = 0;
        
        int[] block = new int[W];
        
        for(int idx = 0; idx<W; idx++)
        {
            block[idx] = sc.nextInt();
        }        
        
        //H는 굳이 필요 없을 듯..
        
        for(int idx = 1; idx<W-1;idx++)
        {
            cur = block[idx];
            
            leftMax = rightMax = 0;
            
            for(int left = 0; left<idx;left++)
            {
                leftMax = Math.max(leftMax,block[left]);
            }
            
            for(int right = idx+1; right<W;right++)
            {
                rightMax = Math.max(rightMax,block[right]);
            }
            int min = Math.min(leftMax,rightMax) - cur;
            
            if(min>=0)
            {
                answer+= min;
            }
        }
        System.out.println(answer);
        sc.close();
    }
}