Baekjoon 17245 서버실 JAVA

17245번: 서버실

문제

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

이 회사의 서버실은 N×N 칸으로 구분되어 있고, 각 칸마다 서버 랙이 있어 컴퓨터를 여러 대 쌓을 수 있다. 서버가 과열되지 않도록 서버실에는 언제나 냉방기가 작동하고 있다. 그런데 회사가 경제적으로 어려움에 처한 나머지, 서버실의 운영 비용을 줄이기 위해 서버실 내의 컴퓨터 중 절반만 정상적으로 관리하기로 하였다.

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

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

 

입력

정수 N이 주어진다. (1 ≤ N ≤ 1000)

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

출력

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

풀이

[알아야 할 점]

문제에서 컴퓨터는 2차원 위치 좌표에 X개가 쌓여있는 형태이다.

 

기본적인 이분탐색을 이용하여 컴퓨터의 높이를 찾아낸다.

최소값 L은 0, 최대값 R은 입력받는 가장 높은 컴퓨터의 높이를 이용한다.

(L+R)/2한 M의 값으로 컴퓨터의 갯수를 더하면서 더해진 높이가 전체 컴퓨터의 절반 이상일 때는 최대값의 갯수를 줄이고,

절반미만일때는 최소값을 높이면서 이분 탐색을 실행한다.

코드

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

public class Main {
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n= Integer.parseInt(br.readLine()), max=Integer.MIN_VALUE;
		long total=0;
		int [][] coms = new int[n][n];
		for(int i=0;i<n;i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				coms[i][j]=Integer.parseInt(st.nextToken());;
				total+=coms[i][j];
				max = Math.max(max, coms[i][j]);
			}
		}
		long l=0, r=max;
		while(l<r) {
			long m=(l+r)/2, temp=0;
			for(int i=0;i<n;i++) {
				for(int j=0;j<n;j++)
					temp+=Math.min(m, coms[i][j]);
			}
			if(temp*2>=total)
				r=m;
			else
				l=m+1;
		}
		System.out.println(r);
	}
}