백준 27932 - 어깨동무 (자바 - 이분탐색)

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

27932번: 어깨동무

 

* 문제 요약

고연전깨 응원을 해 본 양교의 학생들이라면 양 옆 사람들과 어깨동무를 해 본 경험이 있을 것이다! 어깨동무를 할 때 제일 불편할 때가 옆 사람과 키 차이가 많이 날 때이다. 옆 사람들과 키 차이가 나게 되면 응원 동작을 할 때 어깨동무를 하기가 힘들어지고 쉽게 지치게 된다.

그런데 윤헌이는 응원하던 도중, 모든 사람들은 이웃한 사람 중 하나 이상과 키 차이가 H보다 커지면 지친다는 사실을 깨달았다. 그리고 현재 경지 점수 차에 따라서 H의 값이 달라진다는 것도 발견했다!

구체적으로, 고려대가 H점차로 연세대를 이기고 있을 때 고려대 학생들은 자신과 이웃한 사람들과 키 차이가 H가 될 따까지는 지치지 않는다. 고려대와 연세대가 비기고 있다면 H = 0 이 된다. 고려대가 지고 있는 경우는 고려하지 않는다.

윤헌이는 일렬로 선 n명의 고려대생들 중 지친 사람이 k명 이하가 되기 위해서는 고려대가 경기를 최소 몇 점차로 이기고 있어야 하는지가 궁금해졌다. 윤헌이를 위해 이를 구해주자!

 

* 입력

첫 줄에 고려대를 응원하는 학생의 수 n과 지친 사람 수의 최대값 k가 공백으로 구분되어 주어진다.

두 번째 줄에 n명의 학생의 키가 순서대로 공백으로 구분되어 주어진다.

 

* 출력

지친 사람이 k명 이하가 되기 위한 최소 점수차이를 출력한다. 점수 차가 H라고 할 때, 사람들은 옆에 있는 사람들과 키 차이가 H이하이면 지치지 않는다.

 

* 제한

- 1 <= n <= 10^6

- 0 <= k <= n

- i번째 학생의 키를 hi 라고 할 때, 1 <= hi <= 10^9

 

* 예시

 

* 해결 과정

이웃한 사람과 키 차이가 없는 것이 최소, 키가 가장 작은 사람과 키가 가장 큰 사람의 차이가 최대이나, 좀 더 면밀한 계산을 위해 최대의 경우 키가 가장 큰 사람으로 지정했다.

그러므로 start 는 0, end 는 입력받은 값들 중 가장 큰 값이 된다.

이후 다음과 같이 반복문을 진행했다.

1. start <= end 조건을 만족하는 동안 반복문을 진행한다.

  - mid 를 (start + end) / 2 로 초기화한다. 여기서 mid 는 양 팀간의 점수차 H에 해당된다.

  - shoulderStrap(long mid) 메소드를 실행시켜 준다.

    - 각 학생들을 순서대로 탐색하면서 점수차가 mid 일 때 자신의 양 옆사람과의 차이가 H이하인지 아닌지 검사한다.

    - 왼쪽, 오른쪽 중 한 쪽이라도 키 차이가 H를 초과하는 경우가 있을 시 지친 학생 수를 나타내는 변수 count 를 1증가시킨다.

    - 만약 반복문 중간에 count 값이 k를 초과하게 되는 경우 즉시 반복문을 종료한다.

    - 반복문 종료 이후 count 와 k를 비교하여 count 가 k보다 큰 경우 false, 작거나 같은 경우 true 를 반환해준다.

  - shoulderStrap(long mid) 메소드 실행 결과 true 를 반환받은 경우 result 에 현재 mid 값을 저장하고 end 를 mid - 1 로 초기화하여 mid 값이 더 작아지는 방향으로 범위를 줄인다.

  - false 를 반환받은 경우 start 를 mid + 1 로 초기화하여 mid 값이 더 커지는 방향으로 범위를 줄인다.

2. 반복문이 종료된 이후 result 를 출력시켜준다.

 

* 코드

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

    static long[] studentArray = null;
    static int k = 0;

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

        studentArray = new long[n];
        input = br.readLine().split(" ");
        long max = Integer.MIN_VALUE;
        for (int i = 0; i < studentArray.length; i++) {
            studentArray[i] = Long.parseLong(input[i]);
            max = Math.max(max, studentArray[i]);
        }

        if (n == 1) {
            bw.write(0 + "\n");
        } else {
            long start = 0;
            long end = max;
            long result = 0;
            while (start <= end) {
                long mid = (start + end) / 2;

                if (shoulderStrap(mid)) {
                    result = mid;
                    end = mid - 1;
                } else {
                    start = mid + 1;
                }
            }

            bw.write(result + "\n");
        }

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

    }

    private boolean shoulderStrap(long mid) {

        int count = 0;
        for (int i = 0; i < studentArray.length; i++) {
            if (i == 0) {
                if (Math.abs(studentArray[i] - studentArray[i + 1]) > mid) {
                    count++;
                }
            } else if (i == studentArray.length - 1) {
                if (Math.abs(studentArray[i] - studentArray[i - 1]) > mid) {
                    count++;
                }
            } else {
                if (Math.abs(studentArray[i] - studentArray[i + 1]) > mid) {
                    count++;
                } else if (Math.abs(studentArray[i] - studentArray[i - 1]) > mid) {
                    count++;
                }
            }

            if (count > k) {
                break;
            }
        }

        if (count > k) {
            return false;
        } else {
            return true;
        }
    }
}

 

학생들 간에 키 차이가 나지 않는 경우를 고려해 start 를 0, 키 차이가 가장 많이 나는 경우보다 좀 더 넓은 범위를 탐색하기 위해 키가 가장 큰 학생의 키를 end 로 하여 초기 범위를 설정하고,

그 사이의 중간값을 점수차로 지정한 다음 이웃한 학생들간의 키 차이를 비교하며 차이가 중간값보다 큰지 작은지에 따라 지친 학생의 숫자를 계산하고, 그 결과값이 k 보다 크거나 같냐 또는 작냐에 따라 범위를 줄여가며 답을 찾았으므로 매개변수 탐색 문제에 해당된다.