JAEHACHERRY -> 부동소수점 정밀도 오류인줄 알았는데 아닌가요?

  • iyaa
    iyaa

    문자열 중복처리 후, 2차원 배열에 저장합니다.
    처음에는 vector > 로 선언 후, 플로이드 알고리즘을 돌렸는데, 곱하는 횟수가 많아서 그런지 오답이 떴습니다.

    원인을 부동 소수점으로 생각하고 알고리즘을 DFS로 바꾸고, 특정 점에서 0까지 가는 route를 뽑은 후, 그만큼만 곱하는걸로 바꿨는데도 오류가 떴습니다.

    마지막으로, pair로 바꾼 후, 분자와 분모를 구현하여 약분까지 하고 마지막에 딱한번 실수연산 하는데 그거조차 오답이 떠버리네요..

    문제에서도 '두 물건이 비교 불가능한 경우는 없다' 고 했으니, for i in N에서, i~0으로 가는 간선을 DFS를 통해 못찾을리가 없고, 소수점 연산도 딱 한번만해서 오차가 날 수 없다고 생각하는데 이건 도대체 왜 틀리는건지 모르겠습니다..

        #define _CRT_SECURE_NO_WARNINGS
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #include<sstream>
    #include<string>
    #include<vector>
    #include<cmath>
    #include<cstdio>
    #include<cstdlib>
    #include<fstream>
    #include<cassert>
    #include<numeric>
    #include<set>
    #include<map>
    #include<queue>
    #include<list>
    #include<deque>
    #define INF 987654321
    using namespace std;
    int gcd(int a, int b) {

        while (b != 0) {
            int temp = a % b;
            a = b;
            b = temp;
        }

        return abs(a);
    }
    pair<int, int> reduceFraction(int bunja, int bunmo) {
        static int frac[2];
        frac[0] = bunja;
        frac[1] = bunmo;

        if (frac[1] == 0) {
            frac[0] = NULL;
            frac[1] = NULL;

            return make_pair(0, 0);
        }

        int gcd_result = gcd(frac[0], frac[1]);

        frac[0] = frac[0] / gcd_result;
        frac[1] = frac[1] / gcd_result;

        return make_pair(frac[0],frac[1]);
    }



    void dfs(vector<vector<long double> >& adj, int here, vector<bool>& visited, vector<int>& route){
        if (here >= adj.size()){ return; }
        visited[here] = true;
        route.push_back(here);
        for (int i = 0; i < adj[here].size(); i++){
            if (adj[here][i] != 0){
                if (!visited[i]){
                    dfs(adj, i, visited,route);
                }
            }
        }
    }

    void dfs2(vector<vector<pair<int, int> > >& adj2, int here, vector<bool>& visited, vector<int>& route){
        if (here >= adj2.size()){ return; }
        visited[here] = true;
        route.push_back(here);
        for (int i = 0; i < adj2[here].size(); i++){
            if (adj2[here][i] != make_pair(0,0)){
                if (!visited[i]){
                    dfs2(adj2, i, visited, route);
                }
            }
        }
    }

    int main(){
    int T;
    cin >> T;

    while (T--){
    int T2;
    cin >> T2;
    vector<string> A, C;
    vector<long double> B, D;
    for (int i = 0; i<T2; i++){
    string a, c;
    long double b, d;
    cin >> a >> b >> c >> d;
    A.push_back(a);
    B.push_back(b);
    C.push_back(c);
    D.push_back(d);
    }
    int N = 0;
    map<string, int> mapbuf;
    map<int, string> mapbuf2;
    for (int i = 0; i < T2; i++){
    string a = A[i];
    string c = C[i];
    long double b = B[i];
    long double d = D[i];
    if (mapbuf[a] == 0){ mapbuf2[N] = a; mapbuf[a] = N; N++; }
    if (mapbuf[c] == 0){ mapbuf2[N] = c; mapbuf[c] = N; N++; }
    }
    vector<vector<pair<int, int> > > adj2;
    for (int i = 0; i < N; i++){
        vector<pair<int, int> > vbuf2;
    for (int j = 0; j < N; j++){ 
        vbuf2.push_back(make_pair(0, 0));
    }
    adj2.push_back(vbuf2);
    }
    for (int i = 0; i < T2; i++){
    for (int j = 0; j < T2; j++){
    int idx1 = mapbuf[A[i]];
    int idx2 = mapbuf[C[i]];
    adj2[idx1][idx2] = make_pair(B[i], D[i]);
    adj2[idx2][idx1] = make_pair(D[i], B[i]);
    }
    }
    for (int i = 0; i < N; i++){
    adj2[i][i] = make_pair(1, 1);
    }

    vector<long double> retbuf;
    vector<pair<int, int> > retbuf2;
    vector<bool> visited;
    vector<int> route;
    for (int i = 0; i < N; i++){ visited.push_back(false); }
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){ visited[j] = false; }
        route.clear();
        dfs2(adj2, i, visited, route);
        int idx = 0;
        int ja = 1;
        int mo = 1;

        for (int j = 0; j < route.size() - 1; j++){

            if (route[j] == 0){ break; }
            if (adj2[route[j + 1]][route[j]].first != 0 && adj2[route[j + 1]][route[j]].second != 0){
                ja *= adj2[route[j + 1]][route[j]].first;
                mo *= adj2[route[j + 1]][route[j]].second;
            }

        }
        retbuf2.push_back(reduceFraction(ja, mo));
    }
    for (int i = 0; i < retbuf2.size(); i++){
        cout << retbuf2[i].first << " " << retbuf2[i].second << endl;
        retbuf.push_back(retbuf2[i].first / retbuf2[i].second);
    }
    map<long double, vector<string> > ret2;
    for (int i = 0; i < N; i++){
        ret2[-retbuf[i]].push_back(mapbuf2[i]);
    }
    map<long double, vector<string> >::iterator it2;
    for (it2 = ret2.begin(); it2 != ret2.end(); it2++){
        int ssize = it2->second.size();
        sort(it2->second.begin(), it2->second.end());
        for (int i = 0; i < ssize; i++){
            cout << it2->second[i] << " ";
        }
    }

    cout << endl;
    }
    system("pause");
    }
    ~~~

{{DSS04uyexLN6Ql9k}}

    9년 전
1개의 댓글이 있습니다.
  • iyaa
    iyaa

    물론 디버깅용 cout 이런건 전부 출력시 안나오게 처리합니다..


    9년 전 link

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