백준 3079번 입국심사 JAVA 구현해보기

---

```

백준 3079번 입국심사 JAVA 구현해보기

```

이번 글을 통해 배워갈 내용

1. 백준 3079번 풀이

---

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

3079번: 입국심사

 

백준 3079번 입국심사는

난이도 골드 등급의 문제로서

 

입국 심사를 받는 사람들의 수 M

입국 심사대의 수 N

각 입국 심사대의 체크인(심사) 시간들이 주어질 때

 

모두가 입국심사를 받는데 걸리는 최소한의 시간을 찾아주면 됩니다.

 

---

30분 정도 위에 링크를 방문하셔서 풀어보시고

안 풀리시는 경우에만 아래 해답을 봐주시면 감사하겠습니다.

---

시간의 총합을 이분 탐색해서

각 심사대 마다 주어진 시간과 시간의 총합을 통해

 

실제 승객수 보다 적다면 이분 탐색의 왼쪽 극값을 조절해주고

실제 승객수 보다 많거나 같다면 오른쪽 극값을 조절해서 

실제 걸리는 최소 시간을 찾아주면 됩니다.

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    // BufferedReader Object 생성
    static final BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String[] args) throws IOException {

        // 데이터 입력 및 선언
        // checkinDeskCnt 입국 심사대의 수
        // passengerCnt 승객의 수
        StringTokenizer st = new StringTokenizer(br.readLine());
        final long checkinDeskCnt = Long.parseLong(st.nextToken());
        final long passengerCnt = Long.parseLong(st.nextToken());

        // 각 입국 심사대의 체크인 시간들
        List<Long> checkinTimes = new ArrayList<>();

        // leftT 이진 탐색의 왼쪽 극
        // rightT 이진 탐색의 오른쪽 극
        // ans 심사를 받는데 걸리는 최소 시간
        long leftT = 0L;
        long rightT = 0L;
        for (long i = 0L; i < checkinDeskCnt; i++) {
            final long inputNum = Long.parseLong(br.readLine());
            rightT = Math.max(rightT, inputNum);
            checkinTimes.add(inputNum);
        }
        rightT = rightT * passengerCnt;
        long ans = rightT;


        while (leftT <= rightT) {
            final long midT = (leftT + rightT) / 2;
            // 승객수 = 각 심사대 마다 (주어진 시간 / 심사 시간) 의 합
            // tempPsrCnt temp Passenger Counter 임시 승객 카운터
            long tempPsrCnt = 0L;
            for (Long ct : checkinTimes) {
                tempPsrCnt += midT / ct;
            }
            // 임시 추정값이 실제 통과한 승객수보다 작다면
            if (tempPsrCnt < passengerCnt) {
                leftT = midT + 1;
            }
            // 임시 추정값이 실제 통과한 승객수보다 크다면
            else {
                rightT = midT - 1;
                ans = midT;
            }
        }

        System.out.print(ans);

    }
}
//codemasterkimc.tistory.com [김씨의 코딩 스토리]

 

읽어주셔서 감사합니다

 

무엇인가 얻어가셨기를 바라며

 

오늘도 즐거운 코딩 하시길 바랍니다 ~ :)

 

---