[백준][C++] 20300 서강근육맨

20300. 서강근육맨

20300번: 서강근육맨

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

큰 자료형을 써야하는 것 이외에는 쉽게 풀 수 있었던 문제이다.

 

두개의 운동기구에 일어나는 근손실의 합이 최대한 적어야하므로 오름차순으로 정렬해서 가장 큰 값과 작은 값의 합을 구하면 근손실의 합이 적어질 것이다.

 

알고리즘 설계

1. 근손실을 담은 배열을 오름차순으로 정렬한다.

 

2. i부터 배열 사이즈/2까지 반복문을 돌린다.

 

배열 사이즈가 짝수일 경우, 배열[i]와 배열[size - i - 1]의 합을 구하고

홀수일 경우 배열[i]와 배열[size - i - 2]의 합을 구한다.

이렇게 하는 이유는 가장 마지막에 있는 값은 큰 값이므로, 되도록이면 무엇과도 더하지 않는 것이 좋기 때문이다.

 

쉽게 이미지로 표현해봤다.

 

 

3. 합을 구한 값 중 가장 큰 값을 근손실 값으로 한다.

4. 배열 사이즈가 홀수일 경우, 배열의 마지막 요소와 근손실값을 비교해 더 큰 값이 근손실 값이 되게 한다.

// 오름차순 정렬
sort(losings.begin(), losings.end());

// 홀수인 경우 가장 큰 수는 합치지 않는다
int offset = (losings.size() % 2 == 1) ? -2 : -1;

for (int i = 0; i < len / 2; i++)
{
    unsigned long long int loss = losings[i] + losings[losings.size() - i + offset];

    // 최댓값으로 갱신
    if (answer < loss)
        answer = loss;
}

// 계산 안 했던 가장 큰 수와 비교
if (answer < losings.back())
{
    answer = losings.back();
}

cout << answer;

이렇게 구현했다.

 

전체 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<unsigned long long int> losings;
	int len;
	unsigned long long int answer = 0;

	cin >> len;

	for (int i = 0; i < len; i++)
	{
		unsigned long long int input;
		cin >> input;
		losings.push_back(input);
	}

	// 오름차순 정렬
	sort(losings.begin(), losings.end());

	// 홀수인 경우 가장 큰 수는 합치지 않는다
	int offset = (losings.size() % 2 == 1) ? -2 : -1;

	for (int i = 0; i < len / 2; i++)
	{
		unsigned long long int loss = losings[i] + losings[losings.size() - i + offset];

		// 최댓값으로 갱신
		if (answer < loss)
			answer = loss;
	}

	// 계산 안 했던 가장 큰 수와 비교
	if (answer < losings.back())
	{
		answer = losings.back();
	}

	cout << answer;
}

 

처음엔 answer만 unsigned long long으로 했다가... 벡터 요소들과 합친 값loss도 long long이나 unsigned long long을 해줘야 함을 깨달았다.

 

항상 자료형에 주의하자!