취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 26072번 문제인 곰곰이와 시소이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/26072 

받침점의 위치 x가 점점 커지면 커질수록 시소는 점점 왼쪽으로 기울어지는 관계가 있음을 관찰하자. 이를 이용해 x의 위치를 이진탐색(binary search)을 통해 구해낼 수 있다.

탐색 범위가 충분히(문제에서 요구하는 오차범위 이내로) 작아질 때까지 이진탐색을 반복하는 것으로 문제를 해결하자.

아래는 제출한 소스코드이다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long double ld;
typedef pair<int, int> pii;

int N, L;
pii arr[100000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cout << fixed;
	cout.precision(10);

	cin >> N >> L;
	for (int i = 0; i < N; i++) cin >> arr[i].first;
	for (int i = 0; i < N; i++) cin >> arr[i].second;

	ld l = 0, r = L;

	while (r - l > 0.000000001) {
		ld mid = (l + r) / 2;
		ld val = 0;
		for (int i = 0; i < N; i++) {
			ld x = arr[i].first, w = arr[i].second;
			val += (x - mid) * w;
		}

		if (val > 0) l = mid;
		else r = mid;
	}

	cout << (l + r) / 2;
}