SWEA 1245. 균형점 :: 돼지개발자

출저 : https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD&categoryId=AV15MeBKAOgCFAYD&categoryType=CODE

"이분 탐색 과 double.. 100~200 번만 돌리자."

이분 탐색을 통해 문제를 풀어야 한다. 근데 제한 없이 돌리다 보니 stackoverflow... 아래와 같은 게시물을 봄... 결론만 말하자면 double형을 가지고 이분 탐색을 할 경우 100~200 번 까지만 돌리도록 한다는 것이다. (https://www.acmicpc.net/blog/view/37)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Solution {
 
    static int T;
    static int N;
    static int[] X;
    static int[] M;
    
    public static void main(String[] args) throws IOException {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        T = Integer.parseInt(br.readLine());
        int t = 1;
        
        while(T-- > 0) {
            N = Integer.parseInt(br.readLine());
            
            X = new int[N];
            M = new int[N];
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int i = 0; i < N; i++) {
                X[i] = Integer.parseInt(st.nextToken());
            }
            
            for (int i = 0; i < N; i++) {
                M[i] = Integer.parseInt(st.nextToken());
            }
            
            System.out.printf("#%d",t++);
            for (int i = 0; i < N-1; i++) {
                System.out.printf(" %.10f",solve(i,0,(X[i]+X[i+1])/2,X[i],X[i+1]));
            }
            System.out.println();
        }
    }
    
    static double solve(int idx, int depth, double cur, double left, double right) {
        if( depth == 100) return cur;
        double f = 0.0;
        double val = 0.0;
        
        for (int i = 0; i <= idx; i++) {
            f += (double)M[i] / Math.pow(cur - X[i], 2.0);
        }
        
        for (int i = idx+1; i < N; i++) {
            f -= (double)M[i] / Math.pow(X[i] - cur, 2.0);
        }
        
        if(f < 0) {
            val = solve(idx,depth+1, (left + cur)/2.0, left, cur);
        }
        else if ( f > 0) {
            val = solve(idx,depth+1, (cur + right)/2.0, cur, right);
        }
        else {
            val = cur;
        }
        return val;
    }
 
}