BOJ 24981 - Counting Liars

BOJ 24981 - Counting Liars

$N \le 1,000$ 이므로 $O(N^2)$ 로 풀 수 있다.

모든 $p_i$ 에 대해서 모든 조건을 따져본 후 최소 거짓말 횟수를 찾기만 하면 되는 브루트 포스 문제이다.

void solve() {
   int n;
   cin >> n;
   vector<pi> a;
   vi plist;
   for (int i = 0; i < n; i++) {
      string s;
      int p;
      cin >> s >> p;
      if (s == "G") a.pb({1, p});
      else a.pb({-1, p});
      plist.pb(p);
   }
   int ans = 1e9;
   for (int p: plist) {
      int tmp = 0;
      for (int i = 0; i < sz(a); i++) {
         if (a[i].fi == 1) {
            if (p < a[i].se) tmp++;
         } else {
            if (p > a[i].se) tmp++;
         }
      }
      mina(ans, tmp);
   }
   cout << ans;
}