[알고리즘 문제] 1521번 랜덤 소트

1521번: 랜덤 소트

 

1. 문제 분석

N = 8이하 자연수라서 check배열을 이용해 최대 8!의 경우의 수를 구하여 답을 얻을 수 있다. 그리고  bfs와 memoization을 이용해 기댓값을 구하면 된다.

 

2. 실패 과정

실패 과정

살짝 확률을 경우의 수로 정의하는 것과 햇갈려서 횟수의 합과 경우의 수를 나눴다. 솔직히 이래도 괜찮지 않을까? 하고 무심코 넘어갔는데.. 1시간 고민 끝에 틀린 이유를 알 수 있었다. (아래 참고)

 

 

3. 성공 과정

위의 그림에서 쓴 글처럼 사실 어느 것을 선택하느냐에 따라 상황이 완전 달라진다. 또한 321->312->213->123으로 가는 확률이 1/전체 가지수 = 1/5 가 아니라 1/3 * 1/2 = 1/6 이다.

 

이런 논리의 실수로 문제를 이상하게 풀고있다는 것을 깨닫고 어떤 경우를 만드는 기대값을 return함으로 써 다른 수도 갱신해 나갔다...

 

4. 코드

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

int N, arr[11];
map<int,double> chk;

double process()
{
    int check = 1, n = 0, cnt = 0;
    for(int i=0;i<N;i++){
        if(arr[i]>arr[i+1]) check = 0;
        n *= 10, n+=arr[i];
    }
    if(check)
        return 0;
    if(chk[n]) return chk[n];
    for(int i=0;i<N;i++){
        for(int j=i+1;j<N;j++){
            if(arr[i]>arr[j]){
                swap(arr[i],arr[j]);
                double v = process() + 1;
                chk[n] += v, cnt++;
                swap(arr[i],arr[j]);
            }
        }
    }

    return chk[n]/=cnt;
}

int main()
{
    cin>>N;
    for(int i=0;i<N;i++){
        cin>>arr[i];
    }
    arr[N]=100;
    printf("%.9lf", process());
}

 

 

5. 교훈 및 소감

솔직히 이런 실수는 고등학교때 부터 자주 했던 실수인데... 지금도 맞는것 같은데 왜 틀리지... 맞왜틀을 1시간 동안 시전동안 시전하고 있었다.. 통계파트는 싫어서 피하고 있었는데.. 달라지기로 결심했으니 앞으로 통계파트도 열심히 풀어봐야겠다.