취미로 코딩하기

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

이번에 볼 문제는 백준 23365번 문제인 Buffered Buffet이다.
문제는 아래 링크를 확인하자.

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

이 문제의 답은 sum(di) + max(di) - min(di)이다. 이 식 자체는 greedy하게 직관적으로 이끌어낼 수 있으나, 그 엄밀한 증명은 쉽지 않을 수 있다. 이 식이 옳다는 증명은 다음과 같이 수학적 귀납법을 통해 할 수 있다.

i) n=2인 경우, 답은 2*max(di) = sum(di) + max(di) - min(di)이므로 위 식이 성립함을 알 수 있다.

ii) n=k일 때, 이 문제의 답이 sum(di)+max(di)-min(di)라 가정하고, n=k+1일 때의 답을 구해보자.

k+1명 중 di의 값 dX가 가장 큰 한 사람 X를 제외한 k명의 원형 배치를 생각해보자. 벌려야 하는 거리가 dp, dq(단, dp<dq)인 두 사람 사이에 X가 새로 앉을 경우 테이블의 둘레는 dX + (dX-dq)만큼 새로이 증가하게 된다. 따라서 새로 증가하는 거리의 최솟값은 dX + (dX-max(k명의di))가 된다. 이 값은 원형배치에 영향을 받지 않으므로, n=k+1일 때의 답은 min(k명의 원형배치 둘레 거리 최솟값) + dX + dX - max(k명의 di)가 된다. 가정에 따라 min(k명의 원형배치 둘레 거리 최솟값)은 sum(k명의 di) + max(k명의 di) - min(k명의 di)와 같고, min(k명의 di) = min(di), sum(k명의 di) + dX = sum(di), dX = max(di)이므로 식을 정리하면 n=k+1일 때의 문제의 답 또한 sum(di) + max(di) - min(di)가 됨을 확인할 수 있다.

위의 i)과 ii)에 따라 문제의 답은 sum(di) + max(di) - min(di)임이 증명되었다.

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

#include <iostream>
using namespace std;
typedef long long ll;

int N;
ll total = 0, mx = 0, mn = 1000000007;

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

	cin >> N;
	while (N--) {
		ll x; cin >> x;
		total += x;
		mx = max(mx, x), mn = min(mn, x);
	}

	cout << total + mx - mn;
}