[SWEA] Q1245 균형점

[SWEA] Q1245 균형점

Question

Language: Python

Difficulty: D5

처음에는 해당 문제 풀이를 위해 특정 지점에서 거리 a에 대한 좌표를 설정해서 왼쪽 부분의 인력의 합, 오른쪽 부분의 인력의 합을 구해서 같아지는 지점을 찾을려고 하였다. 하지만, 이렇게 접근하게 되면, 너무 풀이가 복잡해져서 풀수가 없다.

두 좌표에 대한 이분탐색을 통해 문제 풀이가 가능한 것을 알게 되었다.

좌표 x₁,x₂에 대한 중간 지점을 잡아서 해당 지점을 기준으로 왼쪽 인력의 합을 구하고, 오른쪽 인력의 합을 구해서 왼쪽 인력의 합이 큰 경우 균형점을 오른쪽으로 이동하고, 그 반대인 경우에는 균형점을 왼쪽으로 이동시킨다.

이런식으로 이분탐색을 수행하면서, 인력의 합이 같아지는 좌표 혹은 인력의 차가 10¹² 이하로 떨어지는 균형점을 구할 때까지 진행한다.

Solution

def binary_search(index):
    left,right=coordinates[index-1],coordinates[index]
    #최대오차범위를 만족하는 구간까지 계속 진행
    while right-left > 1/(10**12):
        mid=(left+right)/2.0

        left_sum=0
        right_sum=0
        #왼쪽 인력의 합
        for left_index in range(0,index):
            left_sum+=(masses[left_index]/(mid-coordinates[left_index])**2)
        #오른쪽 인력의 합
        for right_index in range(index,n):
            right_sum += (masses[right_index] / (coordinates[right_index] - mid) ** 2)
        #오른족 인력의 합이 클 경우 왼쪽 이동
        if left_sum < right_sum:
            right=mid
        #왼쪽 인력의 합이 클 경우 오른족 이동
        elif left_sum > right_sum:
            left=mid
        #인력의 합이 같은 경우 종료한다.
        else:
            break

    return mid

def solution():
    balance_points=[]

    for index in range(1,n):
        balance_points.append(binary_search(index))

    return " ".join(map(lambda x: "%.10f" % x,balance_points))
if __name__ == "__main__":
    with open("input.txt","r" ) as file:
        test_cases=int(file.readline())
        for case in range(test_cases):
            n=int(file.readline())
            inputs=list(map(int,file.readline().split()))

            coordinates=inputs[:n]
            masses=inputs[n:]

            print(f"#{case+1} {solution()}")