SWEA 1245 - 균형점

문제 링크

문제 요약

한 공간의 일직선상에 n개의 자성체가 존재한다. 자성체에서 한 물체에 가하는 인력을 F = Gm1m2/(d*d), (G는 양의 상수 값) 이라고 할 때, 왼쪽에서 작용하는 인력과 오른쪽에서 작용하는 인력의 총 합이 같은 균형점이 n-1개 존재한다.

n개의 자성체의 위치와 질량이 주어질 때, n-1개의 균형점의 위치를 출력하라.

접근

• n-1개의 균형점은 각 자성체들 사이의 n-1개의 구간에 존재함
• 수학을 사용해 균형점의 위치를 역으로 구하긴 힘들기 때문에, 완전탐색을 사용해 해당 위치가 균형점이 맞는지 모두 체크해야 함
• 범위가 넓고 실수값이기 때문에 이분탐색을 이용하기

풀이

1. n개의 위치와 질량 입력받기

2. 각 구간을 따로 나눠 이분탐색 시작

   2.1. mid값을 지정
   2.2. mid값에서의 왼쪽 인력과 오른쪽 인력을 계산해 비교
   2.3. 해당 인력에 따라 left, right 값 갱신
   2.4. 해당 과정을 왼쪽 인력 == 오른쪽 인력일 때까지 반복

주의

• n개의 위치가 먼저 주어진 후, n개의 질량이 한번에 주어짐.
• input값 내에 tab을 이용한 공백이 포함되어 있음. BufferedReader를 쓰며, split(" ") 처리로 값을 구하면 tab을 사용한 공백이 처리되지 않아 Memory error가 날 수도 있음. → trim을 사용해 공백 처리.
• 값 출력 포맷. StringBuilder를 통해 소수를 자릿수 포맷에 맞춰 출력할 때, String.format()을 사용하면 됨.
• 무한루프 처리 → 좌표값의 오차가 10 -12(1e-12) 이하여야 한다고 했기 때문에, left와 right의 차이가 해당 범위 이하일 때 탐색 종료

생각보다 고려해야 하는 내용이 많기 때문에, 구현 주의하기

코드(java/자바)

import java.io.BufferedReader;
import java.io.InputStreamReader;
 
public class SWEA1245 {
 
    static int n, arr[][];
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int testCase = Integer.parseInt(br.readLine())+1;
        String[] str;
        StringBuilder sb = new StringBuilder();
        double left, right, mid=0;
        double res;
         
        for(int tc = 1; tc < testCase; tc++) {
            sb.append('#').append(tc);
            n = Integer.parseInt(br.readLine());
            arr= new int[n][2];
            str = br.readLine().trim().split(" ");
             
            //위치들 한번에 입력받은 후, 질량 한번에 입력받기
            for(int i = 0; i < n; i++) {
                arr[i][0] = Integer.parseInt(str[i]);
                arr[i][1] = Integer.parseInt(str[i+n]);
            }
             
            //각 구간별 서치
            for(int i = 1; i < n; i++) {
                //각 구간에 대한 이분탐색
                left = arr[i-1][0];
                right = arr[i][0];
                while(left < right && right-left > 1e-12) {
                    mid = (left + right)/2;
                    res = cal(mid, i);
                    if(res == 0) {
                        break;
                    }
                    //오른쪽 힘이 더 클 때->더 왼쪽으로 가야함
                    if(res < 0) {
                        right = mid;
                    }else {
                    //왼쪽이 더 클 때->더 오른쪽으로 가야함
                        left = mid;
                    }
                }
                sb.append(" ").append(String.format("%.10f", mid));
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }
     
    //왼쪽과 오른쪽의 인력 합 계산하기
    private static double cal(double mid, int idx) {
        double left, right;
        left = right = 0;
        for(int i = 0; i < idx; i++) {
            left += arr[i][1]/((arr[i][0]-mid)*(arr[i][0]-mid));
        }
        for(int i = idx; i < n; i++) {
            right += arr[i][1]/((arr[i][0]-mid)*(arr[i][0]-mid));
        }
        return left - right;
    }
}