SORTGAME를 알고리즘 문제해결 전략 책의 코드로 했는데 시간초과 떠요..

  • User Avatar
    swqasw

    알고리즘 문제해결 전략의 코드 29.4를 이용해서 문제를 풀었습니다.

    책에서는 n=8인 경우에도 40320개의 상태만 방문하면 되므로 precalc() 수행시간이 오래걸리지 않는다고 적혀있습니다.

    그런데 코드 작성 후 돌려보니 n=8일때 맵 만드는데 한참 걸립니다.

    이유가 무엇인지 알려주시면 감사하겠습니다.

    아래 코드는 책보고 따라한 코드
    ~~~ c++
    #include
    #include
    #include
    #include
    #include
    using namespace std;
    map, int> toSort;
    void precalc(int n) {
    vector perm(n);
    for (int i = 0;i < n;i++) perm[i] = i;
    queue > q;
    q.push(perm);
    toSort[perm] = 0;
    while (!q.empty()) {
    vector here = q.front();
    q.pop();
    int cost = toSort[here];
    for (int i = 0;i < n;i++) {
    for (int j = i + 2;j <= n;j++) {
    reverse(here.begin() + i, here.begin() + j);
    if (toSort.count(here) == 0) {
    toSort[here] = cost + 1;
    q.push(here);
    }
    reverse(here.begin() + i, here.begin() + j);
    }
    }
    }
    }
    int solve(const vector& perm) {
    int n = perm.size();
    //sort(perm, perm + n);
    vector fixed(n);
    for (int i = 0;i < n;i++) {
    int smaller = 0;
    for (int j = 0;j < n;j++) {
    if (perm[j] < perm[i]) ++smaller;
    }
    fixed[i] = smaller;
    }
    return toSort[fixed];
    }
    int main() {
    int testCase;
    cin >> testCase;
    vector result(testCase);
    for (int i = 0;i < testCase;i++) {
    int n;
    cin >> n;
    vector perm(n);
    for (int j = 0;j < n;j++) cin >> perm[j];
    toSort.clear();
    precalc(n);
    result[i] = solve(perm);
    }
    for (int i = 0;i < testCase;i++) {
    cout << result[i] << endl;
    }
    return 0;
    }
    ~~~


    9년 전
1개의 댓글이 있습니다.
  • User Avatar
    sgchoi5 
    for (int i = 1; i <= 8; i++)
    precalc(i);

    를 testCase for 문 전에 미리 해주시면 됩니다. 전처리 후 각 testcase 에서 사용하는 것입니다.


    7년 전 link

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.