BOJ 1521 - 랜덤 소트

BOJ 1521 - 랜덤 소트

순열과 인덱스

우선, 순열을 인덱스로, 인덱스를 순열로 변경하는 방법을 알고 있다면 구현해주자.

모른다면 이 TIP을 보고 구현하자.

사실 이 문제는 인덱스를 순열로 변환하는 과정은 직접 만들 필요는 없다. 왜냐면 $8!=40320$는 작은 수로, c++의 next_permutation 이나 python의 itertools로 미리 다 순회를 한다음 각 인덱스에 순열을 미리 저장해두어도 문제없기 때문이다.

int fac[10], n;  
int perm_to_idx(const vi &p) {  
   int ret = 0;  
  
   for (int i = 0; i < n; i++) {  
      int less = 0;  
      int remain = n - 1 - i;  
      for (int j = i + 1; j < n; j++) if (p[j] < p[i])less++;  
      ret += less * fac[remain];  
   }  
  
   return ret;  
}  
vi idx_to_perm(int i) {  
   vi p(n), unused(n);  
   iota(all(unused), 0);  
   for (int j = 0; j < n; j++) {  
      int k = i / fac[n - 1 - j];  
      p[j] = unused[k];  
      unused.erase(unused.begin() + k);  
      i -= k * fac[n - 1 - j];  
   }  
   return p;  
}

DP의 조건

이제 DP를 다음과 같이 정의하자

$DP[i]=$ $i$ 번째 순열일 때 순열을 오름차순으로 만들기 위해 교환해야 하는 횟수의 기댓값

DP를 사용할 때, DP함수에서 역방향으로 아직 계산중인 값에 접근하는 것은 불가능하다.

이 문제에서 예를 들면, 오름차순으로 $13$번 째 수열에서 $5$번 째 수열의 값을 얻어오고 있는데, $5$번 째 수열을 계산하는 도중 아직 값 계산이 끝나지 않은 $13$ 번 째 수열의 기댓값을 참고하는 행위는 DP가 제대로 성립하지 못한다.

그러나 이 문제는, 문제의 조건대로 두 수를 교환하면 항상 수열의 인덱스가 감소한다는 특징을 가진다.

더 오름차순으로 정렬되기 때문에 인덱스는 감소한다.

따라서 위와 같은 상황이 발생하지 않고 안전하게 DP를 사용할 수 있다.

풀이

$dp[i]$ 를 구하고 있다고 하자. 일단 $i$ 를 순열 $\rm P$로 바꾼다.

(1) 만약 이 순열이 이미 오름차순이라면, 그 인덱스는 $0$ 이라는 것이기 때문에 이 때의 기댓값은 $0$이다. 즉 $0$을 반환한다.

(2) 순열이 오름차순이 아니라면, 교환할 수 있는 모든 쌍의 개수를 센다.

이제 교환할 수 있는 쌍 $P_a, P_b$ 라고 하면, $P_a \leftrightarrow P_b$ 를 바꿔주고 바뀐 순열 $\rm P’$ 의 인덱스를 구해서 $\rm P’$ 의 기댓값을 $\sum$에 더해준다.

여기서 $\sum$ 에는 한 번 교환을 했다는 의미로 $1$ 도 더해주어야 한다.

마지막으로 $\sum$ 을 교환할 수 있는 쌍의 개수로 나누어주어야 한다(평균값).

double fn(int i) {  
   if (i == 0) return 0;  
   double &ret = dp[i];  
   if (ret > -0.5) return ret;  
   ret = 0;  
  
   vi p = idx_to_perm(i);  
   int cnt = 0;  
   for (int j = 0; j < n; j++) {  
      for (int k = j + 1; k < n; k++) {  
         if (p[k] < p[j]) {  
            swap(p[j], p[k]);  
            ret++;  
            ret += (fn(perm_to_idx(p)));  
            swap(p[j], p[k]);  
            cnt++;  
         }  
      }  
   }  
   ret /= cnt;  
   return ret;  
}

전체 코드

double dp[50000];  
int fac[10], n;  
int perm_to_idx(const vi &p) {  
   int ret = 0;  
  
   for (int i = 0; i < n; i++) {  
      int less = 0;  
      int remain = n - 1 - i;  
      for (int j = i + 1; j < n; j++) if (p[j] < p[i])less++;  
      ret += less * fac[remain];  
   }  
  
   return ret;  
}  
vi idx_to_perm(int i) {  
   vi p(n), unused(n);  
   iota(all(unused), 0);  
   for (int j = 0; j < n; j++) {  
      int k = i / fac[n - 1 - j];  
      p[j] = unused[k];  
      unused.erase(unused.begin() + k);  
      i -= k * fac[n - 1 - j];  
   }  
   return p;  
}  
  
double fn(int i) {  
   if (i == 0) return 0;  
   double &ret = dp[i];  
   if (ret > -0.5) return ret;  
   ret = 0;  
  
   vi p = idx_to_perm(i);  
   int cnt = 0;  
   for (int j = 0; j < n; j++) {  
      for (int k = j + 1; k < n; k++) {  
         if (p[k] < p[j]) {  
            swap(p[j], p[k]);  
            ret++;  
            ret += (fn(perm_to_idx(p)));  
            swap(p[j], p[k]);  
            cnt++;  
         }  
      }  
   }  
   ret /= cnt;  
   return ret;  
}  
  
void solve() {  
   fac[0] = 1;  
   for (int i = 1; i < 10; i++) fac[i] = fac[i - 1] * i;  
  
   memset(dp, -1, sizeof dp);  
   cin >> n;  
   vi p(n);  
   fv(p);  
   for (int &i: p) i--;  
  
   cout << fixed << setprecision(15) << fn(perm_to_idx(p));  
}