BOJ (C/C++, Java) 14719번: 빗물

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

---

풀이

dp 등의 방법으로 풀 수 있을 거라 생각했지만 떠오르지 않아 답을 봤다.

현재 위치에서 양옆으로 가장 큰 블럭을 찾고, 현재 위치가 양 옆의 블럭보다 작다면 (양 옆 블럭 중 작은 값 - 현재 블럭)을 고인 빗물 값에 저장하여 출력한다.

---

C/C++ 코드

#include <stdio.h>
#include <algorithm>
using namespace std;

int main() {
    int H, W, sum = 0;
    int blocks[500];

    scanf("%d %d", &H, &W);
    for (int i = 0; i < W; i++) {
        scanf("%d", &blocks[i]);
    }

    for (int i = 0; i < W; i++) {
        int l = 0, r = 0;
        for (int j = 0; j < i; j++)
            l = max(blocks[j], l);
        for (int j = i; j < W; j++)
            r = max(blocks[j], r);

        if (blocks[i] < l && blocks[i] < r)
            sum += min(l, r) - blocks[i];
    }
    printf("%d", sum);
    return 0;
}

 

Java 코드

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

public class Main {
    private static int H, W;
    private static int[] blocks, water;

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] input = bf.readLine().split(" ");
        H = Integer.parseInt(input[0]);
        W = Integer.parseInt(input[1]);

        blocks = new int[W];
        water = new int[W];
        String[] blockInput = bf.readLine().split(" ");
        for (int i = 0; i < W; i++) {
            blocks[i] = Integer.parseInt(blockInput[i]);
            water[i] = Integer.parseInt(blockInput[i]);
        }

        int sum = 0;
        for (int i = 0; i < W; i++) {
            int l = 0, r = 0;
            for (int j = 0; j < i; j++)
                l = Math.max(l, blocks[j]);
            for (int j = i; j < W; j++)
                r = Math.max(r, blocks[j]);

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

        System.out.println(sum);
    }
}