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

이번 글을 통해 배워갈 내용
- 백준 3079번 풀이
https://www.acmicpc.net/problem/3079
3079번: 입국심사
첫째 줄에 N과 M이 주어진다. (1 ≤ N ≤ 100,000, 1 ≤ M ≤ 1,000,000,000) 다음 N개 줄에는 각 심사대에서 심사를 하는데 걸리는 시간인 Tk가 주어진다. (1 ≤ Tk ≤ 109)
www.acmicpc.net
백준 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 [김씨의 코딩 스토리]
읽어주셔서 감사합니다
무엇인가 얻어가셨기를 바라며
오늘도 즐거운 코딩 하시길 바랍니다 ~ :)
728x90
'Java > Java 알고리즘' 카테고리의 다른 글
| 백준 11945번 뜨거운 붕어빵 JAVA 구현해보기 (0) | 2022.05.15 |
|---|---|
| 백준 1145번 적어도 대부분의 배수JAVA 구현해보기 (0) | 2022.05.15 |
| 백준 10822번 더하기 JAVA 구현해보기 (0) | 2022.05.14 |
| 백준 10821번 정수의 개수 JAVA 구현해보기 (0) | 2022.05.14 |
| 백준 9093번 단어 뒤집기JAVA 구현해보기 (0) | 2022.05.14 |