[백준] 14719 - 빗물 (JAVA)

개츠비·2023년 4월 2일

백준

목록 보기

49/84

소요시간 : 45분
문제 사이트 : 백준
문제 수준 : 골드 5
문제 유형 : 구현, 시뮬레이션
다른 사람의 풀이를 참고 했는가 ? : X
한 번 풀었다가 다시 푸는 문제인가 ? : X
문제 링크 : https://www.acmicpc.net/problem/14719
푼 날짜 : 2023.04.02

1. 사용한 자료구조 & 알고리즘

그냥 구현 유형으로 분류될 것 같다.
그리고 나는 그리디 알고리즘도 함께 사용한 것 같다.

2. 사고과정

처음엔 BFS 혹은DFS 로 풀여보려고 했는데 조금 생각해보다가 그렇게 풀기 어려움을 알게 되었다.
그렇게 해서 생각해게 된 게 구현 이다.

👉 예제 입력 1을 본다면
가로축 높이를 기준으로 현재 높이가 3 0 1 4 이고
3에서 부터 시작해서 옆으로쭉 뻗어나가며 3 이상인 높이가 있는지 확인한다.
4에서 처음으로 3 이상인 높이를 발견하고 이제 중간의 높이를 더해줄 수 있다. sum에 3-0, 3-1 을 각각 더해준다. sum은 5.

👉 예제 입력 2를 본다면
가로축 높이를 기준으로 현재 높이가 3 1 2 3 4 1 1 2 이고
3에서 부터 뻗어나가며 3 이상인 높이가 있나 찾는다. 3번쨰 인덱스가 3이므로 처음으로 3 이상인 것을 찾았다. 그러므로 3-1과 3-2를 더해준다. sum은 이제 3.

다음으로 3번째 인덱스부터 다시 탐색을 시작. 4번쨰 인덱스에서 처음으로 3이상인 값을 찾았다. 하지만 그 중간에 있는 숫자는 없으므로 더해주지 않는다.

4번쨰 인덱스부터 다시 탐색을 시작. 7번쨰 인덱스까지 다 찾아도 4번째 인덱스의 값인 4 이상이 없다. 그렇다면 이제 높이를 1 낮춰서 다시 탐색한다.
4번째 인덱스부터 3이상인 값이 있나 없나 탐색 시작. 7번쨰 인덱스까지 다 찾아도 없다. 높이를 1 더 낮춘다.
4번째 인덱스부터 2이상인 값이 있나 없나 탐색 시작. 7번째 인덱스에서 2 이상인 값을 찾았다. 2-1, 2-1 을 각각 더해줘서 sum은 결국 5가 된다.

3. 풀이과정

각각의 높이를 저장
앞서 말한 현재 높이에서부터 내 높이 이상인 값이 있나 없나 탐색한다. 있다면 그 중간의 값을 더해준다.
찾지 못한다면 높이를 1 낮춰서 다시 탐색한다.
높이가 만약 0이 될때동안 찾지 못했다면 결국 중간의 빗물을 더해줄 수 없다고 판단하고 break한다.

4. 소스코드

import java.util.*;
import java.io.*;

public class Main {
	static ArrayList<Long> number=new ArrayList<>();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		st=new StringTokenizer(br.readLine());
		int H=Integer.parseInt(st.nextToken());
		int W=Integer.parseInt(st.nextToken());
		
		int arr[]=new int[W];
		st=new StringTokenizer(br.readLine());
		for(int i=0;i<arr.length;i++){
			arr[i]=Integer.parseInt(st.nextToken());
		}
		
		int sum=0;
		for(int i=0;i<arr.length;i++) {
			int nowHeight=arr[i];
			int index=i+1;
			while(true) {
				if(index>=arr.length&&nowHeight==0) {
					break;
				}
				else if(index>=arr.length) {
					nowHeight--;
					index=i;
				}
				else if(arr[index]>=nowHeight) {
					for(int j=i+1;j<index;j++) {
						sum+=(nowHeight-arr[j]);
					}
					i+=(index-i-1);
					break;
				}
				index++;
			}
			
		}
		
		System.out.println(sum);
		

	}
}