14719 - 빗물 (Java)

 

---

 

문제

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

 

 

풀이

접근을 어떻게 하다가 좀 고민하다가, 나는 가장 긴 블록 기준으로 판별했다.

 

 

가장 긴 블록을 기준으로, 아래부터 좌우를 검사하면 빈 공간 찾아내기가 용이하다.

 

가장 높기 때문에 좌우로 빈 공간이 보이면 카운트하고, 그러다가 같은 행에 블록이 생기면 그 사이에 생긴 빈공간을 더해주면 된다.

 

빈공간이 계속 나왔지만 블록이 나오지 않았다면 옆면이 없는 것이므로 더하지 않으면 된다.

 

나는 입력을 받고, 2차원 배열로 형태를 잡았다.

 

그 다음 가장 큰 블록을 가지고 있는 x 좌표에서 가장 밑의 행부터 좌우로 검사하며 위쪽으로 올라갔다. 

 

코드

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

/**
 * [문제] (https://www.acmicpc.net/problem/14719)
 */

public class Main {

    public static Integer h;
    public static Integer w;
    public static Integer maxXPos = -1;
    public static Integer maxBlockValue = -1;
    public static Integer totalArea = 0;
    public static List<Integer> blocks = new ArrayList<>();

    public void solution() throws Exception {
        inputProcess(); // 입력

        int[][] world = new int[h][w]; 
		
        // 2차원 배열엘 값 설정
        for (int i = 0; i < w; i++) {

            if(maxBlockValue < blocks.get(i)){
                maxBlockValue = blocks.get(i);
                maxXPos = i;
            }

            for(int j= h-1; h-1 - blocks.get(i) < j; j--){
                world[j][i] = 1;
            }
        }
		
        // 가장 큰 값을 기준으로 좌, 우 공간 탐색
        for (int i = h-1; i >= 0; i--) {

            // Left Side
            int spaceCount = 0;
            for (int j = maxXPos; j >= 0; j--) {
                if(world[i][j] == 1){
                    totalArea += spaceCount;
                    spaceCount = 0;
                    continue;
                }
                spaceCount++;
            }

            spaceCount = 0;

            // Right Side
            for (int j = maxXPos; j < w; j++) {
                if(world[i][j] == 1){
                    totalArea += spaceCount;
                    spaceCount = 0;
                    continue;
                }
                spaceCount++;
            }
        }
        System.out.println(totalArea);
    }

    public void inputProcess() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st1 = new StringTokenizer(br.readLine());
        StringTokenizer st2 = new StringTokenizer(br.readLine());

        h = Integer.parseInt(st1.nextToken());
        w = Integer.parseInt(st1.nextToken());

        while (st2.hasMoreTokens()) {
            blocks.add(Integer.parseInt(st2.nextToken()));
        }
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}

 

후기

 

- 이렇게 푸는게 맞나 싶어서 찾아보니 작은 값을 기준으로 정답을 구했더라. 난 완전 시뮬레이션 같은 느낌으로 푼 거 같다..

 

- 굳이 그림과 똑같이 한다고 배열 인덱스를 반대로 했는데, 그냥 뒤집어져있는 2차원 배열로 생각하고 했으면 더 깔끔했을 거 같다.