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 를 순열 P로 바꾼다.
(1) 만약 이 순열이 이미 오름차순이라면, 그 인덱스는 0 이라는 것이기 때문에 이 때의 기댓값은 0이다. 즉 0을 반환한다.
(2) 순열이 오름차순이 아니라면, 교환할 수 있는 모든 쌍의 개수를 센다.
이제 교환할 수 있는 쌍 Pa,Pb 라고 하면, Pa↔Pb 를 바꿔주고 바뀐 순열 P’ 의 인덱스를 구해서 P’ 의 기댓값을 ∑에 더해준다.
여기서 ∑ 에는 한 번 교환을 했다는 의미로 1 도 더해주어야 한다.
마지막으로 ∑ 을 교환할 수 있는 쌍의 개수로 나누어주어야 한다(평균값).
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));
}
Comments