문제 이해 단계
문제 자체는 굉장히 단순하다.
운동을 2개씩 짝지어하는데,
하나가 남을 경우 그건 따로 진행한다.
이런 식으로 진행하는데
2개의 숫자의 합과 남은 하나의 숫자를
최소 값으로 하는 수를 찾는 것이다.
문제 접근 단계
이 문제의 포인트는
주어진 운동의 수가 홀수인가 짝수 인가로 나뉜다.
운동 수가 짝수라면,
무조건 두 수의 합이 최소가 되는 값을 찾아야 한다.
하지만 홀수라면 무조건 하나가 남게 되기 때문에,
최솟값을 산출하기 위해 남을 1개의 수를 찾아야 한다.
일단 최솟값이 되기 위한 방법을 생각해 보자.
당연히 (높은 수) + (낮은 수)를 하는 것이
값을 최소화하는 방법이다.
(가장 높은 수 + 가장 낮은 수), (그다음 높은 수 + 그다음 낮은 수)...
이런 식으로 모두 계산했을 때
가장 높은 값이 답이 된다.
하지만 홀수라면 수가 하나 남게 되는데,
이 수는 가장 높은 수가 되어야 한다.
왜냐하면 가장 높은 수를 빼둬야
(높은 수 + 낮은 수) 연산을 할 때
값을 최소로 할 수 있기 때문이다.
즉,
짝수일 경우 : 답 = (높은 수 + 낮은 수)의 최댓값
홀수 일 경우 : 가장 높은 수를 제외해 두고 (높은 수 + 낮은 수) 연산
을 하고 가장 높은 수와 연산 값의 최댓값이 답이 된다.
문제 구현 단계
sort(list.begin(), list.end());
answer = list[list.size() - 1];
if (list.size() % 2 != 0 && list.size() != 1) list.erase(list.end() - 1);
int sPos = 0;
int ePos = list.size() - 1;
while (sPos < ePos) {
long value = list[sPos] + list[ePos];
if (value > answer)
answer = value;
sPos++;
ePos--;
}가장 주요한 코드이다.
먼저 입력받은 값들을 오름차순으로 정렬한다.
그 이후 최댓값인 마지막 배열로 설정해 두고,
%2를 통해 값이 홀수라면 마지막 값을 빼준다.
리스트가 1개일 경우,
리스트를 하나 빼주는 과정에서
오류가 날 수 있기 때문에, 1인 경우도 제외했다.
이후 sPos -> 가장 낮은 값
ePos -> 가장 높은 값 인덱스로 지정하여
1씩 더하고 빼주었다.
이는 그다음 높은 값과 그다음 낮은 값을 받아
서 서로 더해주는 작업을 뜻한다.
그리고 그게 answer보다 크다면
정답을 answer로 처리해 준다.
사실 이 문제는 이 코드가 전부이기 때문에
더 이상 정리할 것이 없다.
아래에 전체코드를 올려두고 마무리하겠다.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
cin.tie(NULL);
cout.tie(NULL);
ios::sync_with_stdio(false);
int N;
long answer;
vector<long> list;
cin >> N;
while (N-- > 0) {
long value;
cin >> value;
list.push_back(value);
}
// 오름차순 정렬
sort(list.begin(), list.end());
answer = list[list.size() - 1];
if (list.size() % 2 != 0 && list.size() != 1) list.erase(list.end() - 1);
int sPos = 0;
int ePos = list.size() - 1;
while (sPos < ePos) {
long value = list[sPos] + list[ePos];
if (value > answer)
answer = value;
sPos++;
ePos--;
}
cout << answer;
}vector와 answer을 long으로 받은 이유는 조건에서
근손실을 나타내는 값이 10^18이기 때문에
int로 받기에는 오버플로우가
발생할 가능성이 생기기 때문이다.
시행착오
쉬운 문제였기 때문에 시행착오는 따로 없었던 것 같다.