백준 17245 - 서버실 (자바 - 이분탐색)

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

17245번: 서버실

 

* 문제 요약

서버실은 여러대의 서버 컴퓨터들을 안정적으로 운영할 수 있는 환경을 유지하기 위해 설치된 공간을 말한다.

이 회사의 서버실은 N x N 칸으로 구분되어 있고, 각 칸마다 서버 랙이 있어 컴퓨터를 여러대 쌓을 수 있다.

서버가 과열되지 않도록 서버실에는 언제나 냉방기가 작동하고 있다.

그런데 회사가 경제적으로 어려움에 처한 나머지, 서버실의 운영 비용을 줄이기 위해 서버실 내의 컴퓨터 중 절반만 정상적으로 관리하기로 하였다.

냉방기에서 나온 차가운 공기는 서버실의 아래쪽부터 서서히 차오른다. 1분마다 컴퓨터 한 대의 높이만큼 방을 채운다. 이 회사의 서버 컴퓨터는 환경에 매우 민감하여 차가운 공기를 받아야만 동작하고, 그렇지 못하면 장애를 일으킨다.

서버실의 컴퓨터 중 절반 이상이 켜지려면 몇 분이 필요할까?

 

* 입력

정수 N이 주어진다. (1 <= N <= 1,000)

N x N 개의 각 칸에 컴퓨터가 몇 대 쌓여있는지가 입력된다. 한 칸에는 최대 10,000,000 대까지 쌓여있을 수 있다.

 

* 출력

몇 분이 지나야 전체 컴퓨터의 절반 이상이 장애를 일으키지 않고 동작할 수 있는지 출력한다.

 

* 예시

 

* 해결 과정

냉방기를 통해 차가운 공기가 채워진 공간에 존재하는 컴퓨터만이 정상적으로 작동한다.

컴퓨터의 절반 이상이 장애를 일으키지 않고 동작하는지 알아야 하므로 우선 전체 컴퓨터가 총 몇대 있는지를 알아내는 동시에, 이분탐색의 최대 범위를 설정하기 위해 서버실에서 최대 높이에 위치해 있는 컴퓨터의 높이가 무엇인지도 알아낸다.

최대 높이를 알아내고 나면 start 를 0, end 를 컴퓨터 최대 높이로 하여 다음과 같이 이분탐색을 수행한다.

1. 만약 컴퓨터의 총 갯수가 0개인 경우. 즉, 서버실에 컴퓨터가 한 대도 없는 경우 0을 출력해준다.

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

  - mid 를 (start + end) / 2 로 초기화한다. 이때 mid 값은 현재 서버실에 차오른 차가운 공기의 높이에 해당된다.

  - halfCom(int mid) 메소드를 실행시킨다.

    - serverArray 배열 전체를 탐색하면서 현재 탐색중인 값이 mid 보다 작거나 같다면 activeCom 변수에 현재 탐색중인 인덱스의 값을 합산해주고 mid 보다 크다면 mid 값을 합산해준다.

    - ((double) activeCom / (double) sum) * 100 의 결과값이 50보다 크거나 같다면 true 를 반환해준다.

    - 그렇지 않다면 false 를 반환해준다.

    - 위와 같은 연산을 해주는 이유는 서버실에 있는 컴퓨터들의 전체 갯수 대비 정상적으로 작동되는 컴퓨터의 비율이 전체의 절반을 넘어가는지 아닌지에 대해 백분율 계산으로 정확히 알아내기 위해서이다.

    - 만약 이를 activeCom >= sum / 2 와 같이 일반적인 나눗셈으로 알아보려 할 경우 sum 이 85와 같이 홀수인 경우 이를 2로 나누면 42라는 결과가 나오는데, 이는 85의 절반보다 오히려 더 작은값에 해당된다.

    - 위와 같은 이유로 일반적인 나눗셈을 수행하면 데이터의 손실이 발생하여 정상적인 비교가 되지 않게되는 경우가 발생하기 때문에 백분율 계산으로 좀 더 정밀하게 정상적으로 동작하는 컴퓨터의 비율을 알아내야 한다.

  - halfCom(int mid) 메소드 실행결과 true 를 반환받았다면 현재 mid 값만큼 차가운 공기가 차올랐을때 서버실에 있는 컴퓨터들 중 절반 이상이 정상적으로 동작 가능하다는 뜻이므로 result 변수에 현재 mid 값을 저장하고 end 를 mid - 1 로 초기화하여 mid 값이 더 작아지는 방향으로 범위를 줄인다.

  - halfCom(int mid) 메소드 실행결과 false 를 반환받았다면 현재 mid 값만큼 차가운 공기가 차올라도 서버실에 있는 절반 이상의 컴퓨터들이 정상적으로 동작할 수 없다는 뜻이므로 start 를 mid + 1 로 초기화하여 mid 값이 더 커지는 방향으로 범위를 줄여준다.

3. 반복문이 종료되고 나면 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 NumberFormatException, IOException {
        new Main().solution();
    }

    static int[][] serverArray = null;
    static long sum = 0; // 서버실에 들어가 있는 컴퓨터의 총 갯수

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

        int size = Integer.parseInt(br.readLine());
        serverArray = new int[size][size];
        int max = Integer.MIN_VALUE;

        for (int i = 0; i < size; i++) {
            String[] input = br.readLine().split(" ");
            for (int j = 0; j < input.length; j++) {
                int number = Integer.parseInt(input[j]);
                serverArray[i][j] = number;
                max = Math.max(max, number); // 컴퓨터 최대 높이 저장
                sum += number;
            }
        }

        // 컴퓨터가 한 대도 없는 경우
        if (sum == 0) {
            bw.write(0 + "\n");
        } else {
            int start = 0;
            int end = max;
            int result = Integer.MAX_VALUE;
            while (start <= end) {
                int mid = (start + end) / 2;

                // 현재 mid 만큼 차가운 공기가 차올랐을 때 그 범위에 포함되는 컴퓨터의 갯수가(정상적으로 작동하는 컴퓨터가)
                // 전체 컴퓨터 갯수의 절반 이상인 경우
                if (halfCom(mid)) {
                    result = mid;
                    end = mid - 1; // 차가운 공기가 쌓이는 높이가 낮아지는 방향으로 범위 줄이기
                } else {
                    start = mid + 1;
                }
            }

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

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

    private boolean halfCom(int mid) {

        long activeCom = 0;
        for (int i = 0; i < serverArray.length; i++) {
            for (int j = 0; j < serverArray[i].length; j++) {
                if (serverArray[i][j] <= mid) {
                    activeCom += serverArray[i][j];
                } else {
                    activeCom += mid;
                }
            }
        }
        
        // 백분율 정확히 계산
        if (((double) activeCom / (double) sum) * 100 >= 50) {
            return true;
        } else {
            return false;
        }
    }
}

 

컴퓨터가 있을 수 있는 최소 높이, 최대 높이를 초기 범위로 설정하고 중간값을 기준으로 차가운 공기가 차올랐을때 서버실에 있는 컴퓨터들의 절반 이상이 정상적으로 동작하는지 아닌지 여부에 따라 범위를 줄여가며 절반 이상의 컴퓨터들이 동작 가능하게끔 하는 차가운 공기의 최소 높이값을 구했으므로 매개변수 탐색 문제에 해당된다.