BOJ 25401 - 카드 바꾸기

BOJ 25401 - 카드 바꾸기

정답은 최대 $n-2$이다. 왜냐면 아무거나 $2$개 집어서 등차수열이라고 하고 나머지것들을 바꿔주면 되기 때문이다.

$O(n^2)$개의 쌍을 모두 그 두개로 설정해둔 다음 나머지 것들을 거기에 맞춰본다.

$O(n^3)$로 최적의 답을 얻을 수 있다.

void solve() {
  int n; cin >> n; vi a(n); fv(a);
  int ans = n - 2;
  for(int i = 0; i < n ; i++) {
   for(int j = i + 1; j < n ;j++){
      if(abs(a[j] - a[i]) % (j-i) == 0){
         int d = (a[j] - a[i]) / (j - i), cnt = 0;
         for(int k = 0 ; k < n ; k++){
            int need = a[i] + (k-i) * d;
            if(a[k] != need) cnt++;
         }
         ans = min(ans, cnt);
      }
   }
  }
  cout << ans;
}