[B0J]빗물(14719번)

티어 : Gold 5
정답여부 : 오답
알고리즘 유형 : 구현 , 시물레이션
시간 제한 : 1초

 

 

💡문제

2차원 세계에 블록이 쌓여있다. 비가 오면 블록 사이에 빗물이 고인다.

비는 충분히 많이 온다. 고이는 빗물의 총량은 얼마일까?

 

 

💡입력

첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500)

두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치부터 차례대로 W개 주어진다.

따라서 블록 내부의 빈 공간이 생길 수 없다. 또 2차원 세계의 바닥은 항상 막혀있다고 가정하여도 좋다.

 

 

💡출력

2차원 세계에서는 한 칸의 용량은 1이다. 고이는 빗물의 총량을 출력하여라.

빗물이 전혀 고이지 않을 경우 0을 출력하여라.

 

 

💡예제 입력1

4 4
3 0 1 4

 

💡예제 출력1

5

 

 

💡예제 입력2

4 8
3 1 2 3 4 1 1 2

 

💡예제 출력2

5

 

 

💡예제 입력3

3 5
0 0 0 2 0

 

💡예제 출력3

0

 

 

💡문제 분석 

• https://velog.io/@solser12/%EB%B0%B1%EC%A4%80-14719-%EB%B9%97%EB%AC%BC-JAVA

[백준 14719] 빗물 (JAVA)

뭔가 설명을 하면 좀 더 어렵기도 하고 나도 블로그를 보고 이해를 했다.

 

💡알고리즘 설계

1. 각 수를 입력받는다.
2. 각 블록에 값을 벽돌의 수를 넣고 rain에는 그중 가장 큰 값을 배열에 넣어준다.
3.  각 값들을 하나씩 빼서 필요한 빗물을 구해주면 된다.

 

💡시간복잡도

• O(N)

 

💡코드

package Gold.baekjoon_14719;

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

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());

        int[] blocks = new int[W];
        int[] rain = new int[W];
        st = new StringTokenizer(br.readLine());

        int height = 0;
        for (int i = 0; i < W; i++) {
            blocks[i] = Integer.parseInt(st.nextToken());
            height = Math.max(height, blocks[i]);
            rain[i] = height;
        }
        int answer = 0;
        for (int i = W - 1; i >= 0; i--) {    
            answer += rain[i] - blocks[i];
        }
        System.out.println(answer);
        br.close();
    }
}

 

💡 틀린 이유

그냥 값을 넣고 구하고 rain - block 빼면 되는거 아닌가 생각을 했는데 마지막 입력값처럼 하면 고인 빗물이 나오기에 그러면 빗물이 고이지 않는 값은 빼줘야 한다고 생각이 들었다.

 

 

💡 틀린 부분 수정 & 다른풀이

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

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());

        int[] blocks = new int[W];
        int[] rain = new int[W];
        st = new StringTokenizer(br.readLine());

        int height = 0;
        for (int i = 0; i < W; i++) {
            blocks[i] = Integer.parseInt(st.nextToken());
            height = Math.max(height, blocks[i]);
            rain[i] = height;
        }
        height = 0;
        int answer = 0;
        for (int i = W - 1; i >= 0; i--) {
            height = Math.max(height, blocks[i]);
            rain[i] = Math.min(height, rain[i]);
            answer += rain[i] - blocks[i];
        }
        System.out.println(answer);
        br.close();
    }
}

 

 

💡 느낀점 or 기억할정보

어렵다 어려워 ㅠㅠ 오히려 이런 상상문제가 더 어려운거 같다.