알고리즘의 정당성 검사 - RATIO 문제 4가지 다른풀이 judge해봤는데 오답인 풀이랑 정답인 풀이의 차이를 모르겠습니다.

  • lee890211
    lee890211

    RATIO 문제를 총 4가지방법 (3가지 기법) 으로 풀어보았는데요.
    1번째 공식화해서 풀기 (다음%까지의 거리를 이용한 공식과 다음%의 수를 이용한 공식 2가지 사용), 2번째 binary search, 3번째는 그냥 brute force. 일단 brute force는 시간초과로 judge가 불가능했고 2번째는 정답으로 나왔습니다. 근데 1번째 방법은 1번공식 2번공식 둘다 오답으로 나오더군요. 테스트코드이용해서 인풋 무작위생성후 3가지 기법들의 정답을 무한대로 생성해봤는데 틀린 아웃풋이 한개도 나오지 않습니다. 이경우 1번째 방법의 문제점을 찾기위해선 어떻게 해야 하나요? judge의 결과로 알고리즘의 문제가 있음은 알겠으나 어디에 문제가있는지는 모르겠네요 ㅠㅠ 아래 코드 첨부합니다. 테스트코드/1번기법-1,2번 공식/2번기법/3번기법 각각 주석달아놨습니다.

    import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        int cNum = Integer.parseInt(br.readLine());
        for (int i = 0; i < cNum; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            System.out.println(solve(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())));
        }
        br.close();
        //테스트 코드 [풀이1 - 2 - 3 에서 나오는 답] 비교
//      for (;;){
//          long res1;
//          long res2;
//          long x =(long) Math.random()*1000000000+1;
//          long y =(long) Math.random()*x+1;
//          if ((res1=solve(x, y))!=(res2=solveBin(x, y)))
//              System.out.println("case1: "+res1+":"+res2+":"+x+":"+y);
//          if (res2!=(solveSimple(x, y)))
//              System.out.println("case2: "+res1+":"+res2+":"+x+":"+y);
//      }
    }
    //풀이 1
    private static long solve(long N, long M) {
        double coe = (double) M / N;
        int Z = (int) (coe * 100);
        coe -= (double) Z / 100;
        coe = coe * -1 + 0.01;
        if (Z > 98)
            return -1;
        //공식 1
//      long ret = (long) Math.ceil(coe * N * N / (N - coe * N - M));
        Z++;
        //공식 2
        long ret = (long) Math.ceil((Z * N - 100*M) / (100 - Z));
        if ((N + ret - 1) > 0 && (100 * (M + ret - 1)) / (N + ret - 1) >= Z)
            return --ret;
        else if ((100 * (M + ret)) / (N + ret) >= Z)
            return ret;
        else
            return ++ret;
    }
    //풀이 2
    private static long solveBin(long N, long M){
        int Z = (int) (M * 100 / N);
        if (Z > 98)
            return -1;
        long sp =0;
        long ep =N;
        while (sp < ep){
            long mid = (sp+ep)/2;
            if (Z < ((M+mid) * 100 / (N+mid)))
                ep = mid;
            else 
                sp = mid+1;
        }
        return ep;
    }
    //풀이 3
    private static long solveSimple(long N, long M) {
        int Z = (int) (M * 100 / N);
        if (Z > 98)
            return -1;
        int Z_tmp = Z;
        long inc = 0;
        while (Z == Z_tmp) {
            inc++;
            Z_tmp = (int) (100 * (M + inc) / (N + inc));
        }
        if (inc < 0)
            inc = -1;
        return inc;
    }
}

    10년 전
3개의 댓글이 있습니다.
  • 일루
    일루

    테스트는 해보지 않았지만 double의 precision 문제로 오차가 생길 수도 있습니다.

    또한 랜덤 데이터의 경우 최악의 경우에 해당하는 데이터가 잘 만들어지지 않을 수 있는데 이 문제의 경우는 최소 수천 개는 만들어봐야 할 것 같습니다.

    공식 자체를 열심히 본건 아니니 그래도 안된다면 다시 질문을 해주세요 ㅠㅠ


    10년 전 link
  • heekyu
    heekyu

    double precision 문제가 맞네요.
    Z만 다른 것처럼 계산하니까 정답 뜨네요.
    int Z = (int) (M * 100 / N);

    input은 이거 넣어보세요.
    99999950 57999971

    이렇게 공식으로 풀 수도 있군요.
    하나 배워갑니다.

    double precision 관련해서는 자주 하는 실수 모음에도 있는데 아래 링크 참조하세요.
    http://docs.oracle.com/cd/E19957-01/806-3568/ncg_goldberg.html


    10년 전 link
  • lee890211
    lee890211

    답변 주신 두분다 감사합니다 Z를 저렇게 계산한건 coe계산부분이 2번중복되길래 저리 뺀건데 연산 1개줄이려다가 엄청난 버그를 만들고 말았군요 ㅠ 근데 신기하게 공식으로하는건 O(1)이고 이분탐색법은 O(lgN) (케이스1개당 시간복잡도) 인데 속도는 비슷하군요. 겨우 1ms빠르네요.


    10년 전 link

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