문제
N개의 평균 점수(소수점 셋째 자리까지)가 주어질 때, 이 모든 평균이 동시에 가능한 최소 사람 수를 구하라.
입력
첫째 줄에 N, 이후 N줄에 평균 점수가 주어진다.
출력
최소 사람 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 3.000 | 1 |
풀이
사람 수 1부터 1000까지 시도하며, 모든 평균이 해당 인원 수로 성립 가능한지 이분 탐색으로 확인한다.
- 평균을 정수(1000배)로 변환하여 부동소수점 오차를 방지한다
- 인원 수 i에 대해 각 평균 avg가 가능한지 확인한다: 총점 S가 존재하여
S/i = avg이고 S가 유효 범위 내인지 이분 탐색한다 - 모든 평균을 만족하는 최소 인원 수를 출력한다
핵심 아이디어: 인원 수가 최대 1000이므로 브루트포스가 가능하며, 각 평균의 가능 여부는 이분 탐색으로 O(log N)에 확인한다.
코드
package day799;
import java.io.*;
import java.util.*;
public class Day757BOJ1206사람의수 {
static StringBuilder sb = new StringBuilder();
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int N, M, K;
static int[] arr;
public static void main(String[] args) throws IOException {
N = Integer.parseInt(br.readLine());
arr = new int[N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine(), ".");
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
arr[i] = a * 1000 + b;
}
for (int i = 1; i <= 1000; i++) {
if (isPossibleCnt(i)) {
System.out.println(i);
return;
}
}
}
static boolean isPossibleCnt(int cntOfPeople) {
for (int avg : arr) {
int left = 0;
int right = 10 * cntOfPeople;
boolean isPossible = false;
while (left <= right) {
int sumOfScore = (left + right) / 2;
int currentAvg = (sumOfScore * 1000) / cntOfPeople;
if (currentAvg == avg) {
if (currentAvg > 10 * 1000) {
continue;
}
isPossible = true;
break;
} else if (currentAvg > avg) {
right = sumOfScore - 1;
} else {
left = sumOfScore + 1;
}
}
if (!isPossible)
return false;
}
return true;
}
}복잡도
- 시간: O(1000 * N * log M) - M은 총점 범위
- 공간: O(N)