문제 출처 : https://www.acmicpc.net/problem/3079
3079번: 입국심사
문제 상근이와 친구들은 오스트레일리아로 여행을 떠났다. 상근이와 친구들은 총 M명이고, 지금 공항에서 한 줄로 서서 입국심사를 기다리고 있다. 입국심사대는 총 N개가 있다. 각 입국심사관이 심사를 하는데 걸리는 시간은 사람마다 모두 다르다. k번 심사대에 앉아있는 심사관이 한 명을 심사를 하는데 드는 시간은 Tk이다. 가장 처음에 모든 심사대는 비어있고, 심사를 할 준비를 모두 끝냈다. 상근이와 친구들은 비행기 하나를 전세내고 놀러갔기 때문에, 지금 심사
www.acmicpc.net
이 문제는 가벼운 이분탐색 문제로 해결 할 수 있는 문제이다.
필자는 최댓값 설정에서 많이 틀려서 조금 골치 아픈 문제였다.
각각의 몫을 더해 가면서 탐색을 하면 쉽게 풀리는 문제이다.
아래는 해당 문제를 풀이한 소스이다.
|
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
|
#include<stdio.h>
#include<algorithm>
#include <limits.h>
#pragma warning(disable:4996)
using namespace std;
long long int arr[100001];
long long int N, M;
long long int value=LLONG_MAX;
int main()
{
scanf("%lld %lld", &N, &M);
for (int i = 0; i < N; i++)
scanf("%lld", &arr[i]);
sort(arr, arr + N);
long long int min = 0;
long long int max = M * arr[N-1] ;
while (min <= max)
{
long long int mid = (min + max) / 2;
long long int sum = 0;
for (int i = 0; i < N; i++)
sum = sum + (mid / arr[i]);
if (sum >= M)
{
if (value > mid)
value = mid;
max = mid - 1;
}
else
min = mid + 1;
}
printf("%lld", value);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4ftext-decoration:none">Colored by Color Scripter
|
'알고리즘' 카테고리의 다른 글
| 백준 2042번 문제 ( 구간 합 구하기 ) (0) | 2020.02.26 |
|---|---|
| 백준 5397번 문제 ( 키로거 ) (0) | 2020.02.26 |
| 백준 16397번 문제 ( 탈출 ) (0) | 2020.02.18 |
| 백준 9019번 문제 ( DSLR ) (0) | 2020.02.18 |
| 백준 7569번 문제 ( 토마토 ) (0) | 2020.02.18 |
뀨심볼
깃허브 주소는 : https://github.com/hhyc2 입니다~