티스토리 뷰
문제
풀이
구해야 하는 건 기구를 두 개씩 사용해서 일어나는 근손실의 합의 최대를 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;
}
'Algorithm > BOJ' 카테고리의 다른 글
[백준 20302] 민트 초코 (0) | 2020.12.11 |
---|---|
[백준 20301] 반전 요세푸스 (0) | 2020.12.11 |
[백준 20291] 파일 정리 (0) | 2020.12.11 |
[백준 20168, 20182, 20183] 골목 대장 호석 - 기능성, 효율성 (0) | 2020.12.02 |
[백준 20167, 20181] 꿈틀꿈틀 호석 애벌레 - 기능성, 효율성 (4) | 2020.12.01 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- 이분탐색
- 표 편집
- 프로그래머스 위클리 9주차
- 카카오 2020 인턴십
- 파싱
- 유니온파인드
- 트리
- Kakaoblind
- 구현
- 위클리 챌린지
- 누적합
- 2022 카카오블라인드
- 시뮬레이션
- DP
- 카카오 2차코딩테스트
- 프로그래머스 월간코드챌린지
- 2022 카카오 블라인드 코딩테스트
- 백준
- 2021 카카오 블라인드
- 카카오 표 편집
- 투포인터
- 게임이론
- 카카오 인턴십
- 카카오 2021
- 2020 KAKAO BLIND RECRUITMENT
- 2021 KAKAO BLIND
- 프로그래머스
- 동적계획법
- BFS
- 2022 KAKAO BLIND RECRUITMENT
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | |||||
3 | 4 | 5 | 6 | 7 | 8 | 9 |
10 | 11 | 12 | 13 | 14 | 15 | 16 |
17 | 18 | 19 | 20 | 21 | 22 | 23 |
24 | 25 | 26 | 27 | 28 | 29 | 30 |
글 보관함