BOJ_15810_풍선공장

문제 이름 : 풍선공장 (15810번)

문제 분류 : 이분탐색

작성 언어 : C

문제

전북대학교 프로그래밍 경진 대회에서는 ACM-ICPC 스타일을 따라 문제를 해결한 팀에게 그 문제에 해당하는 풍선을 달아준다.

풍선을 담당하는 N명의 스태프가 있다. 스태프마다 폐활량이 다르기 때문에 하나의 풍선을 만드는 데 걸리는 시간은 다양하다.

대회가 시작되고 운영진으로부터 M개의 풍선을 만들어 달라는 의뢰가 들어왔다!

각 스태프가 풍선 하나를 만드는 시간(분) Ai를 알고 있을 때, 풍선 M개를 만들기 위해서 최소 몇 분이 걸릴까?

풍선을 만든 후에 문제를 표시할 것이기 때문에 풍선의 종류는 상관이 없다.

모든 스태프는 풍선을 만드는 데에 정확하게 자신이 말한 시간만큼 걸린다. 예를 들어 스태프 A가 풍선 하나를 만드는 데 5분이 걸린다면, 0분에 만들기 시작해서 5분에 끝난다.

입력

스태프의 수 N과 풍선의 개수 M이 입력된다. (1 < N ≤ 1 000 000, 0 < M ≤ 1 000 000)

다음 줄에 N명의 각 스태프들이 풍선 하나를 만드는 데 걸리는 시간 Ai가 순서대로 주어진다. Ai는 1 000 000 이하의 자연수이다.

출력

M개의 풍선이 다 만들어지는 최소 시간을 출력한다.

예제 입력 1

3 8

5 7 3

예제 출력 1

14

힌트

1, 2, 3번 스태프가 각각 5분, 7분, 3분씩 걸린다면 3분이 지났을 때 3번 스태프가 1개, 5분에 1번 스태프가 1개, 6분에 3번 스태프가 1개를, 7분에 2번 스태프가 1개를, 9분에 3번 스태프가 1개를, 10분에 1번 스태프가 1개를, 12분에 3번 스태프가 1개를, 14분에 2번 스태프가 마지막 1개를 만들면 총 14분으로 최소 시간이 걸린다. 

 

 

 

풀이

 

얼핏보면 알고리즘 없이 수학적으로만 풀 수 있을것같지만 굉장히 어렵다.

 

먼저 입력범위를 살펴보자

스태프 수 최대 100만, 풍선수 최대100만 , 걸리는시간 최대 100만 이니깐

정답은 최소 1부터 (풍선1개, 스태프1명 걸리는시간1)

최대 1조까지 나온다. (스태프 1명이 걸리는 시간 100만일때 , 풍선 100만개를 만들어야하면?)

따라서 int형 (대충 21억) 대신  long long 형을 써줬다.

 

범위가 굉장히 크기때문에 브루트포스같이 배열을 모두 돌며 무작정 계산하는방법은 시간초과가 떠서 쓰지못한다.

따라서 n 또는 log n복잡도를 가지는 알고리즘을 써야만한다. 그래서 이분탐색을 사용했다.

 

스태프 하나가 만드는 풍선의 개수는  (지난시간) / (풍선하나를 만드는데에 걸리는시간) 이다.

이것을 활용해서 시간범위 최소부터 최대까지를 이분탐색으로 탐색하면 된다.

 

 

#include <stdio.h>
#include <stdlib.h>
int main()
{
	int N,M,time,num=0;
	scanf("%d %d",&N,&M);
	int *a;
	a = (int*)malloc(sizeof(int)*1000001);
	long long low=1LL;
	long long high=1000000000001LL;
	long long mid,count;
	for(int i=1;i<=N;i++)
	{
		scanf("%d",&a[i]);
	}
	while(low+1<high) //이분탐색 
	{
		mid = (long long)(low+high)/2;
		count = 0;
		for(int i=1;i<=N;i++) //모든 스태프가 유추한경과시간동안 
		{
			count = count + (long long)(mid / a[i]); //풍선을 얼마나만들수있는지? 
		}
		if(count >= M) 	high = mid; //시간이 충분함 (오른쪽탐색) 
		else			low = mid; // 시간이 더 필요함  (왼쪽탐색) 
	}
	printf("%lli",high);
	free(a);
}

 

 

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

15810번: 풍선 공장