BOJ_14627_파닭파닭

문제 이름 : 파닭파닭 (14627번)

문제 유형 : 이분 탐색

작성 언어 : C

문제

평소 요리에 관심이 많은 승균이는 치킨집을 개업하였다. 승균이네 치킨집은 파닭이 주메뉴다. 승균이는 가게를 오픈하기 전에 남부시장에 들러서 길이가 일정하지 않은 파를 여러 개 구매하였다. 승균이는 파닭의 일정한 맛을 유지하기 위해 각각의 파닭에 같은 양의 파를 넣는다. 또 파닭 맛은 파의 양에 따라 좌우된다고 생각하기 때문에 될 수 있는 한 파의 양을 최대한 많이 넣으려고 한다. (하지만 하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.) 힘든 하루를 마치고 승균이는 파닭을 만들고 남은 파를 라면에 넣어 먹으려고 한다. 이때 라면에 넣을 파의 양을 구하는 프로그램을 작성하시오. 승균이네 치킨집 자는 정수만 표현되기 때문에 정수의 크기로만 자를 수 있다.

입력

첫째 줄에 승균이가 시장에서 사 온 파의 개수 S(1≤S≤1,000,000), 그리고 주문받은 파닭의 수 C(1≤C≤1,000,000)가 입력된다. 파의 개수는 항상 파닭의 수를 넘지 않는다. (S≤C) 그 후, S 줄에 걸쳐 파의 길이 L(1≤L≤1,000,000,000)이 정수로 입력된다.

출력

승균이가 라면에 넣을 파의 양을 출력한다.

예제 입력 1

3 5
440
350
230

예제 출력 1

145

힌트

파닭 하나당 넣을 수 있는 최대 파의 길이는 175cm으로, 440cm 파에서 2개, 350cm 파에서 2개, 230cm 파에서 1개, 총 5개의 파닭을 만들 수 있고, 각각의 파에서 90cm + 0cm + 55cm = 145cm의 파가 남는다.

 

 

 

풀이

저번에 풀었던 이분탐색 문제와 비슷하다

입출력에 유의하면서 (파의길이 10억 , 파의개수 100만 -> int 범위초과)

정답의 범위중에 이분탐색을 해주면 된다.

 

 

작성 코드

#include <stdio.h>
#include <stdlib.h>
int main()
{
	int S,C;
	long long low = 1LL;
	long long mid;
	long long high = 1000000001LL;
	long long count;
	int *a;
	a = (int*)malloc(sizeof(int)*1000001);
	
	scanf("%d %d",&S,&C);
	for(int i=0;i<S;i++)
	{
		scanf("%d",&a[i]);
	}
	while(low+1<high)
	{
		mid = (low+high)/2;
		count=0LL;
		for(int i=0;i<S;i++)
		{
			count += a[i]/mid;
		}
		if(count<C)
		{
			high = mid; //printf("카운트가 없어..\n");
		}
		else 
		{
			low=mid;    //printf("카운트가 많아..\n"); 
		}
		//printf("이분탐색중..%lli %lli %lli 와%lli\n",
		//low,mid,high,count);
	}
	long long sum = 0LL;
	for(int i=0;i<S;i++)
	{
		sum += a[i];
	}
	sum = sum - C * low;
	printf("%lli\n",sum);
	free(a);
}