<Algorithm> 145. 균형점(SWExpert)

1. 균형점(SWExpert)

• 이분탐색 문제

• 이문제는 오차 때문에 애를 먹었다. 하나를 맞추면 다른 하나가 오버플로우 발생하고 또 발생하고 이를 잡는데 시간이 좀 걸렸다.

• 느낀 것은 이분탐색의 횟수를 고정하는 부분, 오차가 문제에서 주어진 것을 쓰는 부분 두가지 생각이 필요하다는 것을 배웠다.

import java.util.Scanner;
 
public class Solution {
    static double[] pairx;
    static double[] wei;
    static double[] answer;
    static int n;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int test = sc.nextInt();
        for(int t = 1 ; t <= test; t++) {
            /******************************
             * 이분탐색을 이용하여 좌표를 찾는다.
             * 이때 좌우인력은 갯수만큼 플러스 된다.
             *******************************/
            n = sc.nextInt();
            pairx = new double[n];
            wei = new double[n];
            answer = new double[n-1];
            for(int i = 0; i < n; i++) {
                pairx[i] = sc.nextDouble();
            }
            
            for(int i = 0; i < n; i++) {
                wei[i] = sc.nextDouble();
            }
            
            for(int i = 0; i < n-1; i++) {
                left_idx = i;
                min = Double.MAX_VALUE;
                count = 0;
                binary(pairx[i],pairx[i+1], i);
            }
            System.out.print("#"+t+" ");
            for(int i = 0; i < n-1; i++) {
                System.out.print(String.format("%.10f", answer[i])+" ");
            }
            System.out.println();
        }
    }
    static int left_idx;
    static double min;
    static int count;
    public static void binary(double start, double end,int idx) {
        count++;
        if(count > 100) {
            return;
        }// 실행 수
        if(start >= end) {
            return;
        }
        double mid = (start + end)/2f;
        double F_left = 0.0;
        double F_right = 0.0;
        
        for(int i = 0; i <= left_idx; i++) {
            F_left += wei[i]/Math.pow(Math.abs(pairx[i]-mid), 2);
        }
        for(int i = left_idx+1; i < n; i++) {
            F_right += wei[i]/Math.pow(Math.abs(pairx[i]-mid), 2);
        }
        
        if(min > Math.abs(F_left-F_right)) {
            answer[idx] = mid;
            min = Math.abs(F_left-F_right);
        }
        if(Math.abs(F_left-F_right) < 1e-13) {
            answer[idx] = mid;
            return;
        }
        
        if(F_left < F_right) {
            binary(start, mid,idx);
        }else if(F_left > F_right) {
            binary(mid, end,idx);
        }
        
    }
}
 

참고 & 출처