백준 - 빗물

문제 링크 ▶︎ 빗물

문제 파악

물이 고이기 위해서는 큰 벽과 작은 벽들, 그리고 큰 벽이 다시 감싸진 구조가 발생해야 그 곳에 물이 고일 수 있고, 큰 벽들 중에서 더 작은 벽의 크기에 맞게 물이 고인다는 사실을 구현하는 것이 중요하다고 생각했다.
그래서 물이 고일 수 있는 조건을 찾는 것에 집중하면서 문제를 풀기로 했다.

접근 방법

1. 물이 고일 수 있는 높이의 최대가 500이므로 for문으로 1부터 최대 높이 h까지 반복하면서 해당 높이에 물이 고일지 말지를 체크한다.

2. 물이 고이는 섹션의 수를 cnt에 저장하고, flag는 좌우에 물이 고이게 만들어주는 높은 칸이 존재하는 지에 대한 변수로 저장한다.

3. 폭만큼 다시 반복문을 돌면서 (500x500이라 괜찮음) 해당 섹션이 현재 높이보다 낮으면 물이 고일 수 있는 건데, flag(물이 고이게 만들어주는 좌우에 높이가 높은 섹션)이 존재한다면 물이 고이는 것이다.

4. 현재 높이보다 해당 섹션이 높다면 그 섹션은 flag로 쓰일 수 있게되고 그 전까지 고인 섹션들은 answer에 저장하고 cnt를 초기화하고 다시 반복문을 수행한다.

코드 구현

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

public 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());
        st = new StringTokenizer(br.readLine());
        int[] arr = new int[w];
        for (int i = 0; i < w; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int answer = 0;
        for (int dep = 1; dep <= h; dep++ ) {
            int cnt = 0;
            int flag = 0;
            for (int i = 0; i < w; i++) {
                if (arr[i] < dep) {
                    if (flag > 0) {
                        cnt += 1;
                    }
                } else {
                    flag += 1;
                    answer += cnt;
                    cnt = 0;
                }
            }
        }
        System.out.println(answer);
    }
}

개선 사항

500x500이라서 두번의 반복문으로 풀었지만, h와w가 커질 시에는 DP나 투포인터로 풀어야하기 때문에 이러한 방법으로 풀어보는 것이 중요할 것 같다.