✔문제링크

SWEA1245. 균형점

📝문제설명

물체와 N개의 자성체에 대한 균형점을 찾는 문제이다. 이때 균형점은 N-1개가 발생한다. 물체와 자성체 사이에 작용하는 인력은 자성체와 물체 사이의 거리(d)와 자성체와 물체의 질량(m)으로 구한다.
자성체로부터 물체에 작용하는 인력을 구하는 공식: F = Gm1m2/(d*d), G는 양의 상수 값

💡해결방법

문제를 이해하는데 오랜시간이 걸렸다. 쉽게 설명하자면 첫번째 자성체와 나머지 자성체가 균형을 이루는 점을 찾고, 다음으로 첫번째, 두번째가 나머지 자성체들과 균형을 이루는 점을 찾는다. 이 과정을 N-1번 반복한다. 나는 이분검색을 이용하여 균형점을 찾아 나갔다.

👍코드

package com.algorithm01.basic;

import java.util.Arrays;
import java.util.Scanner;

public class SWEA1245균형점 {

	public static class point implements Comparable<point>{
		public int x, m;

		public point(int x, int m) {
			this.x = x;
			this.m = m;
		}
		
		@Override
		public int compareTo(point o) {
			return Integer.compare(this.x, o.x);
		}
	}
	
	static int T, N;
	static double ANS;
	static point[] po;
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		T = sc.nextInt();
		
		for(int tc=0; tc<T; tc++) {
			N = sc.nextInt();
			po = new point[N];
			
			for(int i=0; i<N; i++) {
				po[i] = new point(0, 0);
			}
			for(int i=0; i<N; i++) {
				po[i].x =sc.nextInt();
			}
			for(int i=0; i<N; i++) {
				po[i].m =sc.nextInt();
			}
			
			Arrays.sort(po);
			
			System.out.print("#"+(tc+1));
			for(int i=0; i<N-1; i++) {
				double left = po[i].x;
				double right = po[i+1].x;
				System.out.printf(" %.10f", DFS(left, right, 0));
			}
			System.out.println();
			
		}
	}
	private static double DFS(double left, double right, int L) {
		double mid = (left+right)/2;
		if(L == 100) return mid;
		double prev = 0, next = 0; 
		for(int i=0; i<N; i++) {
			double dis = (double)(po[i].x-mid);		//거리
			if(po[i].x <mid) {
				prev += po[i].m/Math.pow(dis, 2); 
			}
			else if(po[i].x > mid) {
				next += po[i].m/Math.pow(dis, 2); 
			}
		}
		
		if(prev == next) return mid;
		else if(prev>next) {
			left = mid;
			return DFS(left, right, L+1);
		}
		else {
			right = mid;
			return DFS(left, right, L+1);
		}
	}
		
}