제2회 곰곰컵 풀이

A - 치킨댄스를 추는 곰곰이를 본 임스 2 풀이
B - 붙임성 좋은 총총이 풀이
C - 곰곰이와 학식 풀이
D - 오락실에 간 총총이 풀이
E - 곰곰이와 시소 풀이
F - 외로운 곰곰이는 친구가 있어요 풀이
G - 곰곰이와 테트리스 풀이
H - 곰곰아 선 넘지마 풀이
I - 곰곰이의 식단 관리 2 풀이
J - 서커스 나이트 풀이

BOJ 26072 - 곰곰이와 시소 링크
(2022.12.01 기준 S2)

문제

N개의 치킨이 있고 L 길이의 시소가 있다.
i번째 치킨은 wi의 무게를 가졌고, 시소의 왼쪽 끝에서 xi만큼 떨어진 위치에 놓여 있다.
시소가 평행하게 만드는 받침점의 위치 출력

알고리즘

이리 보고 저리 봐도 이분 탐색

풀이

받침점에 따라 치킨은 왼쪽이나 오른쪽에 속하게 된다.
그에 따라 왼쪽과 오른쪽의 무게를 구해 받침점을 옮기면 된다.
그런데
식이 다 나와 있다.
식을 그대로 참고하여 왼쪽과 오른쪽의 무게를 구하고
왼쪽 무게가 더 크면 받침점은 왼쪽으로 옮겨야 한다. (이해가 안가면 상상을 해보자.)
오른쪽 무게가 더 크면 받침점은 오른쪽으로 옮겨야 한다.

이를 문제에서 원하는 오차보다 더 작아질 때까지 이분 탐색하면 된다.

코드

import sys; input = sys.stdin.readline

N, L = map(int, input().split())
x = list(map(int, input().split()))
w = list(map(int, input().split()))

# 문제의 노트에 있는 식 그대로 왼쪽과 오른쪽의 무게를 구해
# 왼쪽이 더 무거우면 받침점을 왼쪽으로, 오른쪽이 더 무거우면 받침점을 오른쪽으로 옮겨야 한다.
# 이를 이분 탐색으로 하여금 받침점을 조정해주면 된다.

start = 0; end = L
while end - start > 0.0000001: # 오차가 1e-07보다 작거나 같아질 때까지
    mid = (start + end) / 2 # 현재 받침점
    L = R = 0 # 왼쪽 오른쪽 무게
    for i in range(N):
        # i번째 치킨마다 받침점에 따른 위치를 판정해 왼쪽이나 오른쪽 무게에 더해주자.
        if x[i] < mid: # 받침점의 왼쪽
            L += w[i] * (mid - x[i])
        else: # 받침점의 오른쪽
            R += w[i] * (x[i] - mid)
    if L < R: # 오른쪽이 더 무거우면 받침대가 가능한 범위를 오른쪽으로 선택
        start = mid
    else: # 왼쪽이 더 무거우면 받침대가 가능한 범위를 왼쪽으로 선택
        end = mid

print(start)