[SWEA] 1245. 균형점

문제

1245. [S/W 문제해결 응용] 2일차 - 균형점
일직선 상에 n개의 자성체들이 존재한다. 여기에 한 물체 a를 올려놓으면 각 자성체들과 인력이 작용하여 a가 움직인다. 이때, 양쪽 인력이 평형하여 a가 움직이지 않는 지점을 균형점이라 한다. 균형점들의 좌표를 출력하시오.

• 인력 : F = G*m1*m2/(d*d)

풀이

• 코딩문제가 아니라 수학문제였다면 쉬웠겠다.. (※ 아니다.)
• a의 좌표를 미지수 x로 놓고 풀었다.
• x의 값을 알 수 없으므로 이분탐색으로 찾아갔다. (이 방식이 아니길 바랬는데 최선인가보다.)
• 이 때, 'n개의 자성체가 있다면 n-1개의 균형점이 존재한다.' 라고 문제에서 주어졋으므로, 균형점은 자성체들의 사이에 있다는 뜻이다! 따라서 각 자성체들의 x좌표 ~ 다음 자성체의 x좌표 사이의 범위에서 이분탐색을 진행했다.
• 실수 계산이므로 무한루프에 빠질 수 있다. 또 오차도 발생할 수 있다. double형 변수에서는 100~200번 정도만 반복하면 된다고 한다. 그래서 101번 반복한 후 x좌표를 출력했다. 참고
  (더 진행하더라도 출력할 때 소수점이하 10자리까지만 출력하기 때문에 의미가 없다 ~)

자바코드

import java.util.Scanner;
import java.io.FileInputStream;

class Solution
{	
	static int n=0;
	static double [] px = new double[10];
	static int [] m = new int[10];
	public static void main(String args[]) throws Exception
	{
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		for(int test_case = 1; test_case <= T; test_case++)
		{	
			n = sc.nextInt();
			for (int i=0; i<n; i++) {
				px[i] = sc.nextDouble(); // x좌표
			}
			for (int i=0; i<n; i++) {
				m[i] = sc.nextInt(); // 질량 
			}
			
			System.out.printf("#%d ", test_case);
			for (int i=0; i<n-1; i++) {
				binarySearch(i, px[i], px[i+1]);
			}
			
			System.out.println();
		}
	}
	
	static void binarySearch(int slash, double left, double right) {
		double x=0;
		double sum;
		int cnt = 0;
		while(cnt<=100) {
			x = (left+right)/2.0;
			
			sum=0;
			for (int i=0; i<=slash; i++) {
				sum += gravity(i, x);
			}
			for (int i=n-1; i>slash; i--) {
				sum -= gravity(i, x);
			}

			if (sum > 0) {
				left = x;
			} else if (sum < 0) {
				right = x;
			}
			cnt++;
		}
		System.out.printf("%.10f ", x);
	}

	static double gravity(int idx, double x) {
		return m[idx]/((px[idx]-x)*(px[idx]-x));
	}
}