[C++] 백준/BOJ - 20300 : 서강근육맨

문제 이해 단계

---

 

문제 자체는 굉장히 단순하다.


운동을 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로 받기에는 오버플로우가
발생할 가능성이 생기기 때문이다.

 

 

 

 

시행착오

---

쉬운 문제였기 때문에 시행착오는 따로 없었던 것 같다.