백준 14719번(Java)

문제는 다음과 같다.

예제입력은 다음과 같다.

예제입력
4 4
3 0 1 4

출력
5

---

문제를 처음 본 순간 생각했다.

이야.. 쉽다.. 쉬워..
알고리즘 문제가 아니라면..

스스로에게 근자감이라도 불어넣어주고자 허세 한번 부려주고 시작해보자.

필자는 처음 이 문제를 다음과 같은 단계로 해결해보자고 생각했다.

1. 처음 높이를 저장한다.
2. 기존의 높이보다 크거나 같다면 새로운 높이와 기존의 높이 사이의 빈 칸을 계산하고 기존의 높이에 새로운 높이를 저장한다.
3. 반복한다.

끝..!

은 아니다.
구현이 되어야 끝이 나지..

어떻게 구현을 할 수 있을지 곰곰히 생각했다가..

때려쳤다.

내게 주어진 시간은 이미 지났고 내가 풀 수 없는 문제라는 것을 인정하는 시간이었기 때문이다.

이런 문제조차 풀 수 없는 나.. 얼마나 성장하려고 그러지..?

라는 생각으로 다른 사람의 풀이를 보아서 나의 생각 범위를 넓혀주자.

다른 사람의 접근법은 다음과 같다.

1. 처음과 끝 부분은 물이 찰 수 없다. 때문에 1 ~ n - 1까지 차례로 계산을 한다.
2. 어떻게 계산하느냐!? 바로 현재의 인덱스를 기준으로 왼쪽과 오른쪽을 나누어 가장 큰 높이를 구한다.
3. 왼쪽 인덱스들 중 가장 큰 높이를 구하고, 오른쪽 인덱스들 중 가장 큰 높이를 구한다.
4. 만약 현재의 높이가 왼쪽과 오른쪽, 둘 모두보다 작다면 얼마나 차이가 나는지 계산하고 result에 더한다.
   (물이 차는 부분이라면 얼마나 물이 차는지 계산하고 결과값에 누적하여 더한다.)
5. 왼쪽과 오른쪽 중 최소값을 찾아서 현재의 높이에서 빼주면 해당하는 값이 물이 차오르는 높이 값이다.
6. n - 1까지 모두 계산하면 끝이다. 출력해주는 백준이 문제해결 도장을 찍어준다. 감사히 받아가자.

---

코드는 다음과 같다.

public class Main {
    static int n, m;
    static int[] rain;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        m = Integer.parseInt(st.nextToken());
        n = Integer.parseInt(st.nextToken());

        rain = new int[n];

        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++)
            rain[i] = Integer.parseInt(st.nextToken());

        int answer = 0;
        for(int i = 1; i < n - 1; i++){
            int l = 0, r = 0;

            for(int j = 0; j < i; j++)
                l = Math.max(l, rain[j]);

            for(int j = i + 1; j < n; j++)
                r = Math.max(r, rain[j]);

            if(rain[i] < l && rain[i] < r) answer += Math.min(l, r) - rain[i];
        }

        System.out.println(answer);
    }
}

---

복잡하게 생각하면 한없이 복잡해지고 단순하게 생각하면 한없이 단순해진다.

우리는 여러 문제를 많이 풀어보아서 문제에 난이도에 맞는 생각을 할 수 있도록 하자.

필자는 범위를 기준으로 결과를 구하려고 했지만, 해당 문제는 요소 하나를 기준으로 결과를 누적하여 구하는 문제였다.

이번 문제를 계기로 일단 가장 작은 단위부터 접근해봐야 한다는 생각을 할 수 있었다.

문제의 첫 인상은 무서웠고 끝 인상은 귀여웠다.

기억해두겠어. 14719번.

끝!