티스토리 뷰

Algorithm/BOJ

[백준 20300] 서강근육맨

giiro 2020. 12. 11. 13:40

문제

www.acmicpc.net/problem/20300

 

20300번: 서강근육맨

PT 첫째 날에 $1$과 $4$를 선택하고, 둘째 날에 $2$와 $3$을 선택하고, 마지막 날에 $5$를 선택하면 $M$은 $5$가 되며, 이때가 $M$이 최소일 때이다.

www.acmicpc.net

 

풀이

구해야 하는 건 기구를 두 개씩 사용해서 일어나는 근손실의 합의 최대를 M이라 할 때, 이를 최소화해야 합니다.

"최대의 최소화" 꼴이라 이분 탐색도 가능하지만 그보다 간단하게 근손실의 정도를 오름차순으로 정렬하고, 매칭 되지 않은 오른쪽 끝 값(최대 값)을 왼쪽 끝 값(최소 값)과 매칭시켜주는 방법을 통해 해결할 수 있습니다.

(n이 홀 수일 경우에 한 번은 1개의 기구만 선택해야 하므로 이는 최대 값을 선택한 후, 정렬한 구간 [0 ~ n-2]의 기구들을 매칭 해주면 됩니다. 

 

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
ll ans;
vector<ll> t;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	t.resize(n);
	for (ll& i : t) cin >> i;
	sort(t.begin(),t.end());
	if (n % 2) {
		ans = t[n - 1];
		for (int i = 0; i < (n - 1) / 2; i++)
			ans = max(ans, t[i] + t[n - 2 - i]);
	}
	else {
		ans = t[0] + t[n - 1];
		for (int i = 1; i < n / 2; i++)
			ans = max(ans, t[i] + t[n - 1 - i]);
	}
	cout << ans;
}

 

 

댓글