백준 14575 - 뒤풀이 (자바 - 이분탐색)

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

14575번: 뒤풀이

 

* 문제 요약

도현이는 이번 대회를 준비하면서 거한 저녁 만찬을 예약했다.

하지만 모종의 이유로 요리사들이 모두 천국으로 떠나버렸기 때문에, 도현이는 어쩔 수 없이 평범한 신촌 술집을 뒤풀이 장소로 정할 수 밖에 없었다.

도현이는 우선 각 사람에게 어느정도 마시면 기분이 좋은지(Li) 와, 어느정도 마시면 힘든지(Ri) 를 물어보았다.

각 사람은 Li 미만의 술을 마시면 술이 부족해 기분이 좋지 않고, Ri 를 초과하는 술을 마시면 천국으로 가버릴수도 있다.

도현이는 각 사람들에게 적당량씩 술을 분배하려고 한다.

그런데 신촌 술집이 항상 그렇듯이, 사장님은 도현이에게 T이상의 술을 반드시 팔아줘야만 예약을 잡아주겠다고 엄포를 놓았다.

마침 도현이의 통장엔 정확히 T의 술을 살 수 있는 금액이 들어있었고, 도현이는 정확히 T의 술을 결제하였다.

이제 도현이는 모든 사람 i에게 Li 이상, Ri 이하의 술을 주면서 그 총합이 정확히 T가 되도록 술을 분배하려고 한다. 하지만 안타깝게도 사람들은 자신의 주량을 과대평가하는 경향이 있다.

이에 따라 도현이는 S의 값을 정하고, 각 사람에게 그 사람이 원하는 술의 양이 얼마이던지 관계없이 S이하의 술만을 주려고 한다. 이제 도현이는 술도 결제했고, 주량도 조사했으므로

1. 모든 사람 i가 Li 이상, Ri 이하의 술을 받으면서,

2. 모든 사람이 받은 술의 총합이 정확히 T가 되고,

3. 어떤 사람도 S를 초과하는 술은 받지 않게 할 수 있는, 그러한 S값만 결정하면 된다.

도현이를 도와 조건을 만족하는 S값을 찾아주도록 하자.

 

* 입력

첫째 줄에 대회 참가자의 수 N과 술의 총량 T가 주어진다. (1 <= N <= 1,000, 1 <= T <= 10^9)

둘째 줄부터 N개의 줄에 걸쳐, 각 사람에 대한 Li 와 Ri 값이 주어진다. (1 <= Li <= Ri <= 10^6)

 

* 출력

만약 S의 값과는 관계없이 항상 불가능하다면 첫째 줄에 -1 만을 출력한다.

문제의 조건을 만족하는 S값이 존재한다면 가장 작은 값 하나를 출력한다.

 

* 예시

 

* 해결 과정

모든 사람의 Li ~ Ri 범위 안에 포함되는 값들 중에서 특정 S이하 만큼의 술을 주었을 때 그 총합이 정확히 T가 되게끔 만들어야 한다.

처음 이 문제를 풀 땐 초기에 S값을 지정할 때와 각 사람들에 대해 지정된 S값 이하의 술을 줄 때, 총 두번에 걸쳐 이분탐색을 수행하여 문제를 해결하려고 하였으나 로직이 너무 복잡해진 동시에 문제 제출 때 2퍼센트도 채 넘지 못하고 틀렸습니다 라는 판정을 받았다.

결국 3시간 동안 고민하고 이런저런 시도를 해보다 안되서 다른 사람들의 풀이를 참고하게 되었다.

 

이분탐색을 이용해 모든 사람이 마신 술의 양이 T를 넘기는지에 따라 S값을 구해준다.

이때, 마신 술의 양이 T와 같아야 하는데, T가 되지 않는 경우가 발생할 수 있으므로 탐색전에 각 사람들의 Li ~ Ri 범위를 기준으로 T를 만들 수 있는지 없는지부터 먼저 확인해준다.

- 각 사람들의 Li, Ri 값을 저장할 2차원 배열을 만든다.

- Li 값들의 총합을 저장할 변수 lsum, Ri 값들의 총합을 저장할 변수 rsum 을 만들고 다음과 같이 반복문을 진행해준다.

1. Li, Ri 값을 입력받은 후 2차원 배열의 0번째 열 인덱스에 Li, 1번째 열 인덱스에 Ri 를 저장한다.

2. 배열에 입력받은 Li, Ri 각각의 값들을 lsum, rsum 에 합산해준다.

3. 반복을 통해 lsum, rsum 값이 구해졌으면 다음과 같이 조건문을 처리해준다.

- lsum 이 T보다 크거나, rsum 이 T보다 작으면 -1 을 출력해준다.

-> lsum 이 T를 넘기게 되면 가장 작은 값들을 합친값이 T보다 크다는 뜻이므로 어떤값을 S로 지정해도 총합이 정확히 T가 되는 경우가 존재할 수 없게된다.(어떤 값을 S로 지정해도 총합을 구해보면 반드시 T보다 커진다는 뜻)

또한 rsum 값이 T보다 작은 경우에도 가장 큰 값들을 합친값이 T보다 작다는 뜻이므로 어떤 값을 S로 지정해도 총합이 정확히 T가 되는 경우가 존재할 수 없게된다.(어떤 값을 S로 지정해도 총합을 구해보면 반드시 T보다 작아진다는 뜻)

 

위의 조건을 통과했을 시 다음과 같이 이분탐색을 진행해준다.

1. start 를 0, end 를 T로 초기화한다.

2. start <= end 조건을 만족하는 동안 다음과 같이 반복을 진행한다.

  - mid 를(start + end) / 2 로 초기화한다. 이때, mid 는 S값에 해당된다.

  - S값 이하로 제공된 술의 총량을 합산하기 위한 변수 sum 을 선언해준다.

  - 0 ~ n 까지 계속되는 반복문을 선언하고 만약 반복 탐색도중 Li 값이 mid 보다 큰 값이 발견될 경우. 즉, 어떤값을 S로 지정해도 해당값이 Li 보다 작아서 제대로 만족시켜 줄 수 없는 사람을 찾은 경우 즉시 반복문을 종료하고 start 를 mid + 1 로 초기화하여 mid 가 더 커지는 방향으로 범위를 줄여준다.

  - 그렇지 않을 경우 sum 변수에 현재 탐색중인 사람의 Ri 값과 mid 값중 더 작은 값을 합산해준다.

  (마실 수 있는 최대량이 mid 보다 더 작은 경우가 발생할 수 있는데, 그 경우엔 그 사람이 마실 수 있는 최대치인 Ri 값을 더해주는 것, 만약 Ri 가 아니라 Li 를 기준으로 주게 된다면 총합이 T보다 작아지는 경우가 많아져서 자연스레 이분탐색의 범위가 mid 값이 커지는 방향으로 줄어드는 경우가 많아지면서 결국엔 S의 최소값이 아닌 최대값을 찾게된다.)

  - 만약 sum 값이 T보다 크거나 같다면 end 를 mid - 1 로 초기화하여 mid 값이 더 작아지는 방향으로 범위를 줄인다.

  - 만약 sum 값이 T보다 작다면 start 를 mid + 1 로 초기화하여 mid 값이 더 커지는 방향으로 범위를 줄여준다.

3. 반복문이 끝나고 나면 start 를 출력시켜준다.

 

* 코드

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 t = Integer.parseInt(input[1]);

        int[][] alcohol = new int[n][2];

        // T를 만족할 수 없는 경우
        int lsum = 0;
        int rsum = 0;
        for (int i = 0; i < n; i++) {
            input = br.readLine().split(" ");
            int li = Integer.parseInt(input[0]);
            int ri = Integer.parseInt(input[1]);

            alcohol[i][0] = li;
            alcohol[i][1] = ri;

            lsum += alcohol[i][0];
            rsum += alcohol[i][1];
        }

        int start = 0;
        int end = t;

        if (lsum > t || rsum < t) {
            bw.write(-1 + "\n");
        } else {

            // 이분탐색
            while (start <= end) {
                int mid = (start + end) / 2; // S
                int sum = 0;

                boolean check = false;
                for (int i = 0; i < n; i++) {
                    if (alcohol[i][0] > mid) {
                        check = true;
                        break;
                    }
                    sum += Math.min(alcohol[i][1], mid);
                }

                if (check) {
                    start = mid + 1;
                    continue;
                }

                if (sum >= t) {
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }
            bw.write(start + "\n");
        }

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

 

방법을 알고보니 어렵게 생각할 필요가 없는 문제여서 이분탐색 문제 풀이의 역량이 아직 부족하다는 생각이 들게 된 문제였다.

각 사람의 Li ~ Ri 범위가 주어졌을 때 특정값이 지정된 S에 대해 각 사람의 Li 가 S 보다 큰 경우, Ri 가 S보다 작은 경우에 대한 처리를 너무 어렵게 생각하는 바람에 빙빙 돌아가다가 결국 다른 사람의 문제 풀이에 의존해버렸다.

Li 가 S보다 큰 경우, S가 Li, Ri 범위 안에 들어가 있는 경우, Ri 가 S보다 작은 경우에 따라 처리를 다르게 해주고 그에 맞게 범위를 절반씩 줄여가며 답을 찾았으므로 이분탐색 문제에 해당된다.