[SWEA] #1245 - 균형점

※ 문제에 대한 저작권은 SW Expert Academy에 있습니다.

💡 출처

---

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15MeBKAOgCFAYD 

SW Expert Academy

 

💡 문제

---

[설명]

무중력 공간에 n개의 자성체들이 존재한다.

각 자성체들의 중심점이 자성체의 위치, 즉 공간 좌표(x, y, z)가 된다.

n개의 자성체들의 y와 z의 좌표들은 모두 동일하고 x의 좌표만 다르다.

즉, 그림과 같이 일직선 상에 존재한다고 가정한다.

자성체들의 위치는 어떤 외부의 힘에 의해서도 절대 변경되지 않는다.

이때, 어떤 물체가 n개의 자성체들이 위치한 직선의 임의의 위치에 존재하면 각 자성체로부터 인력이 작용한다.

자성체에서 물체에 작용하는 인력은 자성체와 물체 사이의 거리(d)와 자성체와 물체의 질량(m)으로 구한다.

자성체로부터 물체에 작용하는 인력을 구하는 공식: F = G*m1*m2/(d*d), G는 양의 상수 값

이때, 물체의 왼쪽에 있는 자성체들의 인력과 오른쪽의 자성체들의 인력들에서 더 큰 쪽으로 물체가 이동할 것이다.

양쪽의 힘이 같은 지점에 물체가 있다면 물체는 움직이지 않고 정지 상태가 된다.

물체에 작용하는 양쪽이 힘이 같은 지점을 찾아보자. n개의 자성체가 있다면 n-1개의 균형점이 존재한다.

좌표값의 오차가 10^-12(1e-12) 보다는 작아야 함에 주의하자.

 

[제약 사항]

자성체의 개수 (N)는 2에서 10 사이의 값이다 (2 ≤ N ≤ 10)

 

💡 아이디어

---

이진 탐색을 이용하여 문제를 해결할 수 있다.

일단, 왼쪽 점과 오른쪽 점 사이의 정가운데를 기준으로 인력을 계산한다.

만약 계산한 인력의 값이 0.0보다 크다면 왼쪽의 인력이 더 크다는 의미이므로

인력의 값을 0.0으로 맞추기 위해선 오른쪽으로 이동해야 한다.

그렇기 때문에 정가운데 지점은 정가운데 점으로, 오른쪽 점은 그대로 둔 상태에서 다시 인력을 계산한다.

반대로 인력의 값이 0.0보다 작다면 오른쪽의 인력이 더 크다는 의미이므로

정가운데 지점을 오른쪽 점으로, 왼쪽 점은 그대로 둔 상태에서 다시 인력을 계산한다.

이 과정을 반복하면서 0이 되는 순간을 찾으면 된다.

그리고 모든 점 사이를 같은 방법으로 반복하면 문제를 해결할 수 있다.

하지만 문제에서 중요한 요소가 있는데, 오차는 10^-12(1e-12) 보다 작아야 한다고 했다.

일반적으로 double 형태의 계산은 약 10^-15이다. 그렇기 때문에 정확히 0.0의 값이 나오지 않아 루프에 갇힐 수 있다.

그렇기 때문에 반복문의 탈출 조건을 0.0이 아닌 약 100번 정도의 반복을 하면 해당 오차보다 작아진다고 한다.

https://www.acmicpc.net/blog/view/37

부동소숫점 오류

 

💡 소스코드

---

package SWEA;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

class set {
	double loc;// 좌표
	int m;;// 질량
}

public class SWEA_P1245_균형점 {
	static int N = 0;
	static set[] list;

	public static void main(String args[]) throws Exception {
		System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P1245_input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer sz;
		int T = Integer.parseInt(br.readLine());

		for (int TC = 1; TC <= T; TC++) {
			N = Integer.parseInt(br.readLine());// 좌표의 개수
			list = new set[N];

			for (int i = 0; i < N; i++)
				list[i] = new set();

			sz = new StringTokenizer(br.readLine());

			for (int i = 0; i < N; i++)
				list[i].loc = Double.parseDouble(sz.nextToken());// 좌표 저장

			for (int i = 0; i < N; i++)
				list[i].m = Integer.parseInt(sz.nextToken());// 질량 저장

			System.out.print("#" + TC + " ");
			for (int i = 0; i < N - 1; i++)
				FindBalalcePoint(i, list[i].loc, list[i + 1].loc);
			System.out.println("");
		}
	}

	// BinarySearch로 균형점 찾기
	public static void FindBalalcePoint(int idx, double left, double right) {
		double div = 0.0;
		double sum = 0.0;

		for (int cnt = 0; cnt < 100; cnt++) {
			div = (left + right) / 2.0;
			
			sum = 0.0;

			for (int i = 0; i <= idx; i++)
				sum += calc(i, div);

			for (int i = N - 1; i > idx; i--)
				sum -= calc(i, div);

			if (sum > 0.0)
				left = div;

			else if (sum < 0.0)
				right = div;
		}

		System.out.printf("%.10f ", div);
	}

	// F = G*m1*m2/(d*d) 계산
	static double calc(int idx, double div) {
		return list[idx].m / ((list[idx].loc - div) * (list[idx].loc - div));
	}
}

 

💡 결과

---

문제 자체는 그렇게 어렵지 않은데 오차와 관련된 문제 때문에 해결이 어려웠다.

double형태의 연산 오차는 나도 검색을 통해 새롭게 알게 된 사실이다.

역시 가끔은 혼자의 힘보다 검색이 도움이 될 때도 있는 것 같다....