SNAIL문제 바텀업과 탑다운

  • sth534
    sth534

    문제

    SNAIL

    질문

    SNAIL문제를 교재와 같이 탑다운 방식으로 풀면 정답이 나오는데,
    바텀업 방식으로 풀면 1000 1000과 같은 입력에서 1보다 훨씬 작은 수가 나옵니다.
    예제는 모두 정확하게 풀리고요.
    제 생각에는 double이 오차가 있어서 이런 차이가 나온다고 생각을 했는데, 탑 다운에서는 같은 계산을 하면서 답이 정확히 나오는게 이해가 안되네요.

    어떤 차이가 있는 걸까요...

    바텀업 - 안되는 코드

    바텀업으로 푼 코드입니다. 503 503 넣어도 1이 안되네요.. 그보다 작은 수는 잘되는 거 같습니다

    #include <iostream>
    
    using namespace std;
    
    int main(){
        double dp[1001][1001] = {0., };
    
        dp[0][0] = 1;
        dp[1][1] = 0.25;
        dp[1][2] = 0.75;
        for(int day = 2; day <= 1000; day++){
            for(int dis = 1; dis <= 1000; dis++){
                dp[day][dis] = dp[day-1][dis-1] * 0.25 + dp[day-1][dis-2]*0.75;
            }
        }
    
        int T;
        cin >> T;
    
        while(T--){
            int n, m;
            cin >> n >> m;
            double res = 0.;
            for(int dis = 0; dis < n; dis++){
                res += dp[m][dis];
            }
            cout.precision(10);
            cout.setf(ios::showpoint);
            cout << 1.0-res << endl;
        }
    

    탑 다운 - 되는 코드

    탑다운으로 푼 코드입니다.
    정답이구요.

    #include <iostream>
    using namespace std;
    double dp[1001][1001] = {0., };
    
    double snail(int dis, int day){
        if(day == 0 && dis == 0) return 1.;
        if(day == 0) return 0;
        if(dis < 0) return 0;
        if(dp[dis][day] != -1) return dp[dis][day];
        dp[dis][day] = snail(dis-1, day-1) * 0.25 + snail(dis-2, day-1) * 0.75;
        return dp[dis][day];
    }
    
    int main(){
    
        int T;
        cin >> T;
    
        while(T--){
            int n, m;
            cin >> n >> m;//거리, 날짜
    
            for(int i = 0; i <=1000; i++){
                for(int j = 0; j <= 1000; j++)
                    dp[i][j] = -1;
            }
    
            cout.precision(10);
            double res = 0;
            for(int dis = 0; dis < n; dis++){
                res -= snail(dis, m);
            }
            cout << res << endl;
        }
    
        return 0;
    }
    

    무슨 차이가 있는 걸까요


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