👀 문제
https://www.acmicpc.net/problem/14719
👊 도전
1. 설계
- i 위치 기준 왼쪽과 오른쪽에서 가장 높은 높이를 구한다(자신 포함).
- ‘왼쪽 오른쪽 중 작은 높이-내 높이’가 i 위치에서 빗물 넓이이다.
2. 구현 (성공 코드)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
import java.util.*;
import java.io.*;
/**
* @author HEESOO
*
*/
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st=new StringTokenizer(br.readLine());
int h=Integer.parseInt(st.nextToken());
int w=Integer.parseInt(st.nextToken());
int[] height=new int[w];
st=new StringTokenizer(br.readLine());
for(int i=0;i<w;i++) { // 높이 저장
height[i]=Integer.parseInt(st.nextToken());
}
int sum=0;
for(int i=0;i<w;i++) {
int left=i;
for(int l=i;l>=0;l--) { // 왼쪽에서 가장 큰 높이 구하기
if(height[l]>height[left]) left=l;
}
int right=i;
for(int r=i;r<w;r++) { // 오른쪽에서 가장 큰 높이
if(height[r]>height[right]) right=r;
}
int size=Math.min(height[left], height[right])-height[i];
if(size>0) sum+=size;
}
System.out.println(sum);
}
}
3. 결과
🤟 성공 🤟
4. 설명
- 왼쪽과 오른쪽에서 큰 높이를 구한다
- i번째 빗물 넓이는 왼쪽과 오른쪽의 큰 높이 중 작은 값을 택한 곳 만큼 올라가 있다.
- 거기서 본인 높이를 빼면 넓이이다(i번째의 w는 1이므로 넓이 계산은 필요 없다).