반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
Tags
- 물채우기
- 이분탐색
- Docker
- 성적평가
- 연결요소
- 경력
- BFS
- 처우협의
- upper_bound
- BOJ
- 백준
- 13908
- softeer
- boj #19237 #어른 상어
- incr
- 파라메트릭
- 소프티어
- OFFSET
- @P0
- dfs
- Kafka
- compose
- 매개변수탐색
- 퇴사통보
- msSQL
- 처우산정
- 6987
- 백트래킹
- 기술면접
- 오퍼레터
Archives
- Today
- Total
기술 블로그
3079번 입국심사 본문
728x90
반응형
https://www.acmicpc.net/problem/3079
이분 탐색 파라메트릭 서치 결정값 boj 백준 필수 복습 코테 코딩 최적화 공부
"이 시간(초) 동안 입국 심사를 모두 완료할 수 있는가?"
예제 1 설명
에를 들어 30초 일 때,
30 / 7 = 4
30 / 10 = 3
-> 7명이다.
m(6)보다 크므로 Right = mid(30) - 1로 하면서 계속 줄인다.
28초라고 할 때,
28 / 7 = 4
28 / 10 = 2
6명이다.
계속 진행을 해보면 28이 최솟값임을 알 수 있다.
핵심은
1.
해당 시간(Time) 동안 입국 심사대에서 입국 심사를 모두 완료할 수 있는 인원 수
= Time / 해당 입국 심사대에서 심사하는데 걸리는 시간
2.
최댓값은 입력으로 주어진 입국 심사대에서 걸리는 시간 중 최댓값과 m을 곱하여 Right로 설정하는 것이다.
이다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 | #include<bits/stdc++.h> using namespace std; #define LL long long LL n, m, Max; vector<LL> v; int main() { //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin); cin.tie(0); scanf("%lld %lld", &n, &m); v.assign(n, 0); for (int i = 0; i < n; i++) { scanf("%lld", &v[i]); Max = max(Max, v[i]); } sort(v.begin(), v.end()); LL Left = 0, Right = Max * m + 1; LL answer = LLONG_MAX; while (Left <= Right) { LL mid = (Left + Right) / 2LL; LL total = 0; for (int i = 0; i < n; i++) { total += (mid / v[i]); } if (total < m) { // total이 m보다 작다면 정답은 [mid, Right]에 있다. // 즉, mid 늘리면 total이 커질 것이고, m에 더욱 가까워 지기 위해 mid + 1을 Left에 대입한다. Left = mid + 1; } else { // m 이상이라면 최대한 줄인다. answer = min(answer, mid); Right = mid - 1; } } printf("%lld\n", answer); // or Left return 0; } | cs |
728x90
반응형
'알고리즘 문제 > BOJ' 카테고리의 다른 글
7579번 앱 (0) | 2020.03.19 |
---|---|
1866번 택배 (0) | 2020.03.18 |
3020번 개똥벌레 (0) | 2020.03.17 |
1301번 비즈 공예 (4) | 2020.03.15 |
4348번 막대 정사각형 (0) | 2020.03.15 |