BOJ 19576 - 약수

문제

가장 큰 완전그래프를 구하는 문제로 환원될 수 있지만, 그건 이 문제에서 요구하는 것이 아니다.

생각해보면 divisor 관계로 완전그래프의 크기는 중복되는 수가 없다면 굉장히 작게 제한되는 조건이다.

$a,~b,~c~\small(a<b<c)$라고 할 때, $b$가 결정된 후 $c$는 최소 $2b$라는 조건이 생겨버리기 때문이다.

이 경우 $a\,\vert\,c$ 임은 자명하다.

수열을 오름차순 정렬하고 $dp_{i,~j}$를 다음과 같이 정의한다.

$dp_{i,~j}=$ 현재 $i$번 째 숫자이고 마지막으로 $j$번 째 숫자를 집합에 넣어주었을 때
끝까지 수열을 순회했을 때 완전그래프 집합의 최대 크기

시간복잡도 $O(N^2)$ 으로 돌려주면 된다.

void solve() {
   int n;
   cin >> n;
   vi a(n);
   fv(a);
   sort(all(a));
   a.insert(a.begin(), 1);
   vvi dp(n + 1, vi(n + 1, -1));
   function<int(int, int)> fn = [&](int i, int j) -> int {
      if (i == n + 1) return 0;
      int &ret = dp[i][j];
      if (~ret) return ret;
      ret = fn(i + 1, j);
      if (a[i] % a[j] == 0) {
         ret = max(ret, 1 + fn(i + 1, i));
      }
      return ret;
   };
   cout << n - fn(1, 0);
}