백준 27172번 - 수 나누기 게임 [C++]

https://www.acmicpc.net/problem/27172

솔브드 클래스 5의 골드 4문제.

 

일단 $N$범위 체크하고 10만인 것을 확인했다. $O(N^2)$ 브루트포스는 당연히 불가.

$x$의 최댓값이 100만이었고, 비슷한 문제를 봤었기 때문에 수학 문제 그 중에서도 소수 판정. 에라토스테네스 체 냄새가 강하게 났다.

흠... 어떻게 풀어야 하지... 내가 생각한게 맞나? 계속 의심이 들었고 결국 백준 태그를 까봤다.

역시 내가 맡은 냄새가 맞았다.

내 뇌가 더욱 강하게 에라토스테네스 체를 단순히 사용하는 쪽으로 치우쳤다.

 

[실책]

우선 플레이어들의 수를 오름차순으로 정렬한다.

정렬된 수를 하나씩 확인하면서 현재 보고있는 수와 나누어 떨어지는 소수 그리고 지금 수를 소수와 나눈 수에 대해 각각 승 패를 결정해준다.

단, 대결을 해볼 때 그 수가 현재 보고 있는 수보다 작아야 한다. (중복 방지)

 

구현하면서 느꼈어야 했는데... 이게 진짜 골드4 수준의 구현은 아닌 것 같은데.. (여러 디테일이 필요했기 때문이다.)

=> 실패한 C++17 코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;
const int LIMIT = 1e6;

void solve() {
  // 에라토스테네스 체 전처리
  vector<int> prime;
  int chk[LIMIT + 1]{};
  for (int i = 2; i * i <= LIMIT; i++) if (!chk[i])
    for (int j = i * i; j <= LIMIT; j += i) chk[j] = 1;
  for (int i = 1; i <= LIMIT; i++) if (!chk[i]) prime.push_back(i);
  
  int n; cin >> n;
  vector<int> vec(n), origin(n);
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
    origin[i] = vec[i];
  }
  sort(all(vec));
  int memo[LIMIT + 1]{}, ans[LIMIT + 1]{};
  for (int i = 0; i < n; i++) {
    int x = vec[i];
    for (auto p : prime) {
      if (p * p > x) break;
      if (x % p == 0) {
        if (memo[p]) { // 수 p가 나온 적이 있으면
          ans[x]--;
          ans[p]++;
        }
        if (p != (x / p) && memo[x / p]) { // 수 x / p가 나온 적이 있으면
          ans[x]--;
          ans[x / p]++;
        }
      }
    }
    memo[x]++; // 수 x가 나온 적이 있음을 기록
  }
  for (int i = 0; i < n; i++) cout << ans[origin[i]] << ' ';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

하지만 이 방법은 틀렸다. 내 뇌가 오로지 소수에만 집중했었다. 그래서 다음과 같은 반례를 생각하지 못했다.

3
2 4 16

 

위의 방법대로 16을 처리한다고 생각했을 때, 소수 2와 3에 대해서만 16을 나눠본다. 그런데 4와는 대결하지 않는다.

 

왜 내가 이걸 처음부터 생각하지 못했을까?

=> 예제에만 집중하여, 수의 약수를 판별하면서 소수로만 나눠보면 모든 약수를 구할 수 있겠구나! 라고 생각했다. (+ 감이 많이 떨어진 점도 있다)

 

[풀이 1]

사실 이 풀이를 적용하고 싶진 않았다. 왜냐하면 결론적으로, 시간복잡도가 \( O(N\sqrt{M}) \)이기 때문이다.

그래서 N이 최대 10만이고, \( \sqrt{1000000} = 1000 \)이기 때문에 곱해서 1억에 가까운 루프를 돌게된다.

 

위의 실책에서의 풀이와 거의 유사하다. 바뀐 점은 전처리해둔 소수들과 나누어서 판단하는 것이 아닌, 1부터 지금 보고있는 수의 제곱근까지 모두 나누어 대결해보는 것이다.

 

* 참고 - 여기서 제곱근까지 하는 이유는 $x_i$가 합성수일 경우 $x_i = n * m$로 나타낼 수 있는데, $n$과 $m$ 동시에 둘 다 \( \sqrt{x_i} \)보다 큰 수가 될 수 없기 때문이다.

 

풀이1 C++17 코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;
const int LIMIT = 1e6;

void solve() {
  int n; cin >> n;
  vector<int> vec(n);
  int chk[LIMIT + 1]{}, ans[LIMIT + 1]{};
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
    chk[vec[i]] = 1;
  }
  for (auto x : vec) {
    for (int i = 1; i * i <= x; i++) if (x % i == 0) {
      if (chk[i]) {
        ans[x]--;
        ans[i]++;
      }
      if (i != (x / i) && chk[x / i]) {
        ans[x]--;
        ans[x / i]++;
      }
    }
  }
  for (auto x : vec) cout << ans[x] << ' ';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}

 

[풀이 2]

풀이 1이 마음에 들지 않았기 때문에 백준 맞힌 사람의 코드와 구글링을 통해 배우게 되었다.

에라토스테네스 체를 응용한 방법이라고 볼 수 있다. (이 때문에 에라체 태그가 달린 듯)

* 참고 - 에라토스테네스 체 시간 복잡도는 \( O(n\ log\ log\ n) \)이다.  문서 자료

 

먼저 플레이어의 수를 모두 저장해둔다.

플레이어의 수 $x_i$를 하나씩 보면서 $x_i * 2$부터 $1'000'000$까지 $x_i$를 더해가며(= 에라체 메커니즘) 자신을 나눌 수 있는 다른 플레이어의 수가 있는지 확인하면 된다.

 

왜 $x_i * 2$부터 시작하고 $x_i$를 더하는가?

=> 어떤 수가 $x_i$를 나눌 수 있는지 생각해보면 된다. $x_i$의 배수만 $x_i$를 나눌 수 있다.

 

아직 내 수학 실력이 부족한 탓에 시간복잡도는 잘 모르겠지만 최악의 경우일 때 약 1200만 번 루프를 돌게 되고, 확실히 빠르다는 것을 알 수 있었다.

 

풀이 2 C++ 17 코드

#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL_TEST
constexpr bool isLOCAL = true;
#else
constexpr bool isLOCAL = false;
#endif

#define debug if constexpr (isLOCAL) cerr

typedef long long ll;
typedef pair<int, int> pii;
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()

const int MOD = 1e9 + 7;
const int INF = 1e9;
const int LIMIT = 1e6;

void solve() {
  int n; cin >> n;
  vector<int> vec(n);
  int chk[LIMIT + 1]{}, ans[LIMIT + 1]{};
  for (int i = 0; i < n; i++) {
    cin >> vec[i];
    chk[vec[i]] = 1;
  }
  for (auto x : vec) {
    for (int i = x + x; i <= LIMIT; i += x) if (chk[i]) {
      ans[x]++;
      ans[i]--;
    }
  }
  for (auto x : vec) cout << ans[x] << ' ';
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  solve();
  debug << "\nTime elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
  return 0;
}