광재는 전자기기 대여사업을 시작했다. 퇴근하기 전에 다음날 손님들에게 빌려줄 N개의 전자기기를 충전하려 한다. 사용 가능한 콘센트는 M개가 있고, 성능은 모두 동일하다.
전자기기들은 한 번에 하나의 콘센트에서만 충전이 가능하고, 충전에 필요한 시간은 2^k(0 ≤ k ≤ 15, k는 정수) 형태이다.
광재의 빠른 퇴근을 위해 모든 전자기기를 충전하기 위한 최소 시간이 얼마인지 알려주자.
입력
첫째 줄에 전자기기의 개수 N과 콘센트의 개수 M이 주어진다. (1 ≤ N ≤ 10,000, 1 ≤ M ≤ 10)
둘째 줄에 충전에 필요한 시간 ti를 나타내는 N개의 정수가 주어진다. (20 ≤ t(i) ≤ 2^15, t(i) = 2^k (0 ≤ k ≤ 15, k는 정수))
출력
충전에 필요한 최소 시간을 출력한다.
예제 입력 1
5 2 1 4 4 8 1 |
예제 출력 1
9 |
더보기
Solution
#include<stdio.h>
#include<stdlib.h>
int compare(const void *x,const void *y)
{
return *(int *)x>*(int *)y?1:*(int *)x==*(int *)y?0:-1;
}
int main(void)
{
int N, M, *t=NULL, *time=NULL, max=0;
scanf("%d%d", &N, &M);
t=(int *)malloc(N*sizeof(int));
time=(int *)calloc(M,sizeof(int));
for(int i=0;i<N;i++)
scanf("%d", &t[i]);
qsort((void *)t,(size_t)N,sizeof(int),compare);
for(int i=N-1;i>=0;i--)
{
int min=0;
for(int m=0;m<M;m++)
min=time[min]>time[m]?m:min;
time[min]+=t[i];
}
for(int m=0;m<M;m++)
max=time[m]>max?time[m]:max;
printf("%d\n", max);
free(time);
free(t);
return 0;
}
728x90
'백준 알고리즘' 카테고리의 다른 글
<백준 알고리즘> 1874번: 스택 수열 (0) | 2022.02.17 |
---|---|
<백준 알고리즘> 15904번: UCPC는 무엇의 약자일까? (0) | 2021.12.29 |
<백준 알고리즘> 1260번: DFS와 BFS (0) | 2021.12.13 |
<백준 알고리즘> 1021번: 회전하는 큐 (0) | 2021.12.12 |
<백준 알고리즘> 1072번: 게임 (0) | 2021.08.02 |