[백준/C++] 3753 Internet Service Providers

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

 

코드

#include <iostream>
using namespace std;

#define FASTIO ios::sync_with_stdio(false);cin.tie(NULL);
typedef long long ll;

ll ternary_search(ll n, ll c) {
	if (n == 0) return 0;

	ll l = 0, r = c / n;

	while (r - l > 3) {
		ll m1 = l + (r - l) / 3;
		ll m2 = r - (r - l) / 3;

		ll p1 = m1 * (c - m1 * n);
		ll p2 = m2 * (c - m2 * n);

		if (p1 > p2) r = m2;
		else l = m1;
	}

	ll ans = l;
	ll profit = ans * (c - ans * n);

	for (ll i = l + 1; i <= r; i++) {
		ll tmp = i * (c - i * n);

		if (tmp > profit) {
			profit = tmp;
			ans = i;
		}
	}

	return ans;
}

int main() {
	FASTIO;
	
	ll n, c;

	while (cin >> n >> c) {
		cout << ternary_search(n, c) << "\n";
	}

	return 0;
}

코드 설명

기본적으로 EOF를 만날 때까지 n, c를 입력받고 삼분탐색을 진행한다. 이때 삼분탐색이란 unimodal한 함수에서 최댓/최솟값을 찾는 탐색법이다. 

 

문제에서 주어진 식은 f(t) = t * (c-t *n)으로 최댓값을 갖는 이차함수이다. 함수의 최댓값을 찾아 출력하는 문제이므로 구간을 나눠 탐색을 진행한다. 이때 n이 0이라면 당연히 최댓값은 0이 되기 때문에 바로 반환하고, n이 0이 아닌 경우에 대해서 확인한다. 

 

이때 탐색할 범위의 최솟값은 0이고, 최댓값은 c/n이다. 구간을 세 개로 쪼갠 후 각 구간의 경곗값 m에 대한 함수값 p를 구한다. 이때 p1 > p2라면 m2 구간 이후부터는 함수값이 감소하는 구간이므로 탐색 범위의 오른쪽 경계를 m2로 바꿔주고, p1 < p2라면 m1 구간 이전의 함수값은 f(m1)보다 작은 값이 위치할 테니 탐색 범위의 왼쪽 경계를 m1으로 바꿔준다.

 

이렇게 탐색을 진행하다가 구간의 크기가 작아지면 이제 직접 함수에 값을 대입해서 확인한다. 리턴되는 값이 (문제에서 요구하는 조건을 충족하는) 함수의 최댓값이 된다.

노란색 선이 탐색을 진행하는 구간입니다

 

느낀 점

이차함수에서 최댓값을 찾는 문제다. 작년 11월에 이 문제를 처음 보고 이차함수의 최댓값을 바로 구하도록 문제를 풀었는데 틀렸다... 삼분탐색을 공부하다가 다시 이 문제가 생각나서 다시 풀어봤다! 이번에는 한 번에 맞았다. 틀렸던 코드를 다시 봤는데 경계 값 처리가 부족했던 것 같다.