백준 27940 - 가지 산사태 (자바 - 그리디)

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

27940번: 가지 산사태

 

* 문제 요약

농장은 총 N 층으로 구성되어 있으며 제일 낮은곳이 1층, 제일 높은곳이 N 층이다.

폭우 소식이 들려왔는데 땅이 경사져 비가 많이 오면 흙이 쓸려 내려가면서 농사를 망칠수도 있다.

기상예보에서 비를 맞는 층과 그 양을 확인할 수 있었다.

비는 총 M 번 쏟아지며, i 번째 비가 오는 순간 농장의 1층 부터 ti 층이 동시에 빗물을 각각 ri 만큼 받게된다.

땅에 스며든 빗물은 증발하지 않는다. 따라서 각 층이 받은 빗물의 양은 마지막 비가 내린 직후까지 누적된다.

 

각 층은 최대 K 만큼의 빗물을 받아도 쓸려 내려가지 않는다. 만약 어떤 층에서 누적된 빗물의 양이 K 를 초과한다면 해당 층은 무너진다. 비가 와서 무너지는 층이 동시에 여러곳 발생할 수도 있다.

농장의 한 층이라도 무너지기 전에 가지를 모두 수확하려고 한다. 몇번째 비가 온 직후 어떤 층이 무너지는지 예측해보자.

 

* 입력

첫째 줄에 농장의 층수 N, 비가 오는 횟수 M, 각 층이 버틸 수 있는 빗물의 양을 나타내는 정수 K 가 주어진다.

(1 <= N <= 10^5, 1 <= M <= 10^6, 1 <= K <= 2 x 10^9)

둘째 줄부터 M 개의 줄에 걸쳐 각 줄에 비의 정보를 나타내는 정수 ti, ri 이 주어진다.

(1 <= ti <= N, 1 <= ri <= 10^9)

모든 ri 의 합은 2 x 10^9 를 초과하지 않는다.

 

* 출력

i 번째 비가 온 직후 처음으로 무너지는 층이 발생할 때 첫째 줄에 i 와 무너지는 층을 아무거나 하나 출력한다.

모든 비가 온 후에 어떤 층도 무너지지 않는다면 -1 을 출력한다.

 

* 예시 

 

* 해결 과정

m 만큼은 반복문을 통해서 모두 입력을 받되, 어느 층이 먼저 무너질지는 생각하지 않아도 된다.

최초로 특정 층이 무너지는 상황이 생긴다면 반드시 1층이 거기에 포함되어 있을것이기 때문에 최초로 무너지는 시점 하나만 고려해주면 된다.

최초로 층이 무너지는 순간 그 중 하나만 출력해주면 되기 때문에 그냥 무조건 1층만 출력해줘도 어차피 스페셜 저지 문제라 정답으로 처리된다.

 

* 코드

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

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

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);
        int m = Integer.parseInt(input[1]);
        long k = Long.parseLong(input[2]);

        long firstFloor = 0;
        boolean check = true;

        for (int i = 0; i < m; i++) {
            input = br.readLine().split(" ");

            int t = Integer.parseInt(input[0]);
            int r = Integer.parseInt(input[1]);

            if (check) {
                // 1층은 반드시 최초로 무너지게 되어 있음
                firstFloor += r;

                if (firstFloor > k) {
                    bw.write((i + 1) + " " + 1 + "\n");
                    check = false;
                }
            }
        }

        if (check) {
            bw.write(-1 + "\n");
        }

        bw.flush();
        bw.close();
        br.close();
    }
}

 

특정 층이 무너지는 상황이 발생하면 반드시 거기에 1층이 포함되어 있을것이기 때문에 어느 층이 무너질지는 고려하지 않고, 오직 최초로 특정 층이 무너지는 상황만을 고려했다.

매 단계마다 1층의 상태를 확인하면서 최초로 무너지는 순간을 찾는 식으로 문제 풀이를 최적화 하였으므로 그리디 알고리즘에 해당된다.