[Algorithm]BOJ 17245 서버실

금요일부터 가장 고생한 문제. 너무 고생해서 답을 찾기도 했고, 그만큼 주의할 점도 많아서 복기할 겸 기록하려고 한다.

package Algoritm.day5;

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

public class no17245 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int N = Integer.parseInt(br.readLine());
        int[][] serverRoom = new int[N][N];
        long all_count = 0;
        int max = 0;
        int min = 0;

        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; j++) {
                serverRoom[i][j] = Integer.parseInt(st.nextToken());
                all_count += serverRoom[i][j];
                if (max < serverRoom[i][j]) {
                    max = serverRoom[i][j];
                }
            }
        }

        int mid = 0;
        while (min + 1 < max) {
            mid = (min + max) / 2;
            long cnt = 0;

            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (serverRoom[i][j] > mid) {
                        cnt += mid;
                    } else {
                        cnt += serverRoom[i][j];
                    }
                }
            }

            if (((double) cnt / all_count) >= 0.5) {
                max = mid;
            } else {
                min = mid;
            }
        }
        System.out.println(max);
    }
}

• 1번째로 고생한 부분은 이진탐색하는 방법 그 자체였다.
  
  탐색 결과를 빠져나오게하는 타이밍이 언제인지를(...) 꽤나 고민했는데,
  최대값과 최소값의 차이가 1이 되는 순간부터는, mid값이 계속 같은 값이 나오게 되는 무한루프의 형태가 되는 걸 알 수 있었다.
  때문에, 이진탐색을 사용하는 반복문에서의 범위가 아래와 같아지는 걸 알 수 있다.

        while (min + 1 < max) 

• 2번째는 또 자료형...이었는데 ㅎ...ㅎ
  문제에 제시 된 범위가 주어진 배열의 최대 크기는 (1 ≤ N ≤ 1000)
  배열의 한 칸에 쌓일 수 있는 컴퓨터의 최대 대수는 10,000,000여서,
  안전하게 int의 범위에 전부 들어온다고 생각해서 모든 변수에 자료형 int를 붙여서 풀었었다.
  이제 생각을 못한 부분은 배열의 칸마다 최대 107의 컴퓨터가 있고, 그 배열의 칸수가 최대여서 103라고 생각한다면, 존재하는 모든 컴퓨터의 대수를 더하는 all_count 변수의 경우 1010이 되버릴 수도 있는데, 그럼 Int의 범위를 벗어나서 자료형에서 오류가 발생할 수 있다는 부분이다. ㅎㅎ 자료형.. 범위..항상 조심하자 !

자료형 때문에 숫한 난장판을 겪었다...ㅎㅎ 좋은..배움이었다...

cf) Int의 범위
2-31 ~ (231-1) / -2,147,483,648 ~ 2,147,483,647