BOJ 1206 - 사람의 수

BOJ 1206 - 사람의 수

오랜만에 푸는 수학 문제(사칙연산 안해본지 2년지남)라 쉬운건데도 헤맸다.

---

이 문제가 까다로운 점은 소수점 처리에 있다. 하지만 이는 정수를 이용한 계산으로 변형이 가능하다.

항상 $3$자리수까지 주어지므로 $5.672 \rightarrow 5672$ 처럼 $1000$을 곱해서 다룬다고 생각해보자.

사람이 $1000$명이 있다면 항상 모든 점수를 만들 수 있으므로 사람수는 최대 $1000$명이다. 예를 들어, $3.224$라는 평균 점수는 $3.224 = \dfrac{3224}{1000}$ 이고 $1000$명이 총합 $3224$ 점을 내게 되면 만들어지기 때문이다.

현재 확인하는 사람수가 $i$ 라고 하자. 그럼 사람이 내는 점수에도 $1000$을 곱하므로 $0, 1000, 2000 \cdots 10000i$ 까지의 범위가 총점이 될 것이다.

그럼 이 점수의 집합을 $S$ 라고 하자.

그럼 우린 모든 $n$개의 점수에 대해서 $\text{score}_j = \dfrac{S_x}{i} ~~(1 \le j \le n)$ 임을 만족하는 $x$ 가 $S$ 내에 존재하는지 검사하면 된다.

이는 $O(1000 \cdot N \cdot 10000)$ 정도가 된다.

아래의 코드는 $S$ 내에서 존재하는 $x$ 가 있는지 단순히 모두 검사하는 것이지만 간단한 수식으로 $O(10000)$ 을 뗄 수 있다.

void solve() {  
   int n;  
   cin >> n;  
   vi a;  
   for (int i = 0; i < n; i++) {  
      string s;  
      cin >> s;  
      auto v = spliti<int>(s, ".");  
      a.pb(v[0] * 1000 + v[1]);  
   }  
  
   for (int i = 1; i <= 1000; i++) {  
      // S = {a | 0 ~ i * 10000 까지 1000 단위로}  
      // 이 총점을 k라고 할때, 1 <= j <= n 을 만족하는 모든 정수 j에 대해  
      // a[j] = S_x / i 를 만족하는 x가 존재하는가?  
      int success = 1;  
      for (int j = 0; j < n; j++) {  
         int check = 0;  
         for (int sum = 0; sum <= i * 10000; sum += 1000) {  
            if (a[j] == sum / i) {  
               check = 1;  
               break;  
            }  
         }  
         if (!check) {  
            success = 0;  
            break;  
         }  
      }  
  
      if (success) {  
         cout << i;  
         return;  
      }  
   }  
}