[그리디 #11] BOJ 20300 - 서강근육맨

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

20300번: 서강근육맨

 

접근 방법

중요한 점)

1. 근손실 M을 넘지 않도록 설정한다는 것.

2. 하루에 운동 기구를 2개씩 사용

3. 홀수 일이면 마지막 날은 1개만 사용

 

이를 종합하면 2개씩 짝지은 합이 최소가 되고, 홀수 일 경우 가장 큰 값을 혼자 남겨놔야 최소가 된다.

 

따라서, 알고리즘은 다음과 같다.

 

전제: 오름차순 혹은 내림차순으로 정렬 / 마지막 값을 비교 대상(res)으로 설정

i) 짝수일 경우.

가장 큰 것과 가장 작은 것을 서로 짝지어서 합과 res를 비교

 

ii) 홀수일 경우.

가장 큰 값을 제외한 나머지를 가장 큰 것과 가장 작은 것을 서로 짝지어 합과 res를 비교

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n;

vector<long long> v;

int main() {
	long long tmp;

	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> tmp;
		v.push_back(tmp);
	}

	sort(v.begin(), v.end());

	int i = 0;
	int j = n-1;
	if (j % 2 == 0)	j--;

	long long res = v[n-1];
	while (i < j) {
		if (res < v[i] + v[j])
			res = v[i] + v[j];

		i++; j--;
	}
		
	cout << res;
}

값의 범위를 신경써주자...

int일 경우, 표현 범위를 넘어서 틀림!!