백준 3079번: 입국심사 (Python/Java)

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

3079번: 입국심사

 

 

 

접근

---

이분 탐색은 결국 정렬되어 있는 범위 혹은 배열을 반씩 나누어 탐색하는 방법이다. 즉, 범위의 최솟값과 최댓값을 아는 것이 중요하다. 해당 문제에서 가장 최소로 나올 수 있는 시간 값은 가장 짧은 심사 시간이다. 최대로 나올 수 있는 시간은 가장 긴 심사시간에 모든 친구들이 심사를 받았을 때, 즉 '가장 긴 심사시간*친구 수'다.

 

이 범위를 중심으로 이분 탐색을 해본다. 설정한 최솟값과 최댓값의 중간값을 구한다. 그 뒤 가장 짧은 시간이 걸리는 심사 시간을 나눠본다. 이는 총 심사 시간(중간값) 동안 해당 심사관에게 심사받을 수 있는 친구의 수를 뜻한다.

 

이렇게 구한 심사받을 수 있는 친구의 수 합이 총 친구 수보다 많거나 같으면 해당 값은 답이 될 수 있다. 해당 값을 따로 저장해 두고 최댓값을 중간값에서 1 뺀 값으로 설정한 뒤 다시 중간값을 구하고 반복한다. 만약 심사받을 수 있는 친구 수 합이 총 친구수보다 적으면 해당 값은 답이 될 수 없다. 이는 곧 심사 시간이 조금 더 길게 필요하다는 것을 의미한다. 최솟값을 중간값에서 1을 더한 값으로 설정한 뒤 다시 중간값을 구하고 반복한다. 이를 반복하면 문제 조건에 맞는 심사시간을 구할 수 있다.

 

 

 

풀이

---

Python

gateNum, friendNum = map(int, (input()).split())

board = []
for i in range(gateNum):
    board.append(int(input()))

board = sorted(board)

start, mid, last = board[0], 0, (board[(gateNum-1)]*friendNum)
result = 0
while start <= last:

    mid = (start + last)//2

    subResult = 0
    for i in range(gateNum):
        subResult += mid//board[i]

        if subResult >= friendNum:
            break

    if subResult >= friendNum:
        result = mid
        last = mid - 1
    else:
        start = mid + 1

print(result)

 

Java

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    
    public static void main(String[] args) {
        
        Scanner scan = new Scanner(System.in);

        String[] firstLine = (scan.nextLine()).split(" ");
        int gateNum = Integer.parseInt(firstLine[0]), friendNum = Integer.parseInt(firstLine[1]);

        long[] board = new long[gateNum];
        for(int i = 0 ; i < gateNum ; i++){
            board[i] = Long.parseLong(scan.nextLine());
        }

        Arrays.sort(board);

        long start = board[0], mid = 0, last = (board[(gateNum-1)]*friendNum);
        long result = 0;
        while(start <= last){

            mid = (start + last)/2;

            long subResult = 0;
            for(int i = 0 ; i < gateNum ; i++){
                if(subResult >= friendNum){
                    break;
                }
                
                subResult += (mid/board[i]);
            }

            if(subResult >= friendNum){
                result = mid;
                last = mid - 1;
            }else{
                start = mid + 1;
            }

        }

        System.out.println(result);

    }

}

 

 

 

후기

---

며칠 전에 풀었던 백준 16564번 문제(https://www.acmicpc.net/problem/16564)와 사실상 같은 문제다. 조건을 읽자마자 바로 같은 문제임을 알았지만 지난번에 조금 헷갈려했던 부분이 있었기에 다시 한번 제대로 풀어보자는 생각으로 풀었던 문제. 다른 알고리즘과 섞였다거나 복잡한 조건이 들어가 있는 문제가 아니었기에 최댓값, 최솟값 설정만 하면 금방 풀 수 있는 문제였다... 라고 생각했다.

 

여기서 문제는 java 풀이의 범위 설정이었다. 분명 python코드와 같은 로직이고 범위 설정도 제대로 했다고 생각했는데 오답처리가 되었다. 문제는 각 심사관 별 걸리는 시간이었다. 문제 조건 상, 각 심사대에서 심사를 하는 데 걸리는 시간은 1 보다 크거나 같고 10^9보다 작거나 같았다. 분명 int 타입으로 받을 수 있는 범위였음에도 불구하고 long 타입으로 받아야 정답처리가 되었다. 이 부분은 아직도 미스테리인데, 다시 체크해봐야 할 것 같다.