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

1. 문제이해

20300번: 서강근육맨 (acmicpc.net)

20300번: 서강근육맨

 

서강헬스클럽에 비치된 운동기구의 개수(N)과 각 운동기구의 근손실정도(t)가 주어진다.

향빈이는 PT를 받을 때, 근손실정도가 최소가되도록 최대 하루에 2개씩 운동기구를 사용하려고 한다.

이때, PT를 한번 받을 때의 근손실 정도(M)의 최솟값을 출력하는 알고리즘을 구현하는 것이 목표이다.

 

 

 

2. 문제풀이

 

오늘도 그리디 문제이다.

N개의 운동기구를 적절히 조합하여 근손실이 최소로 발생하도록 하면 되는 문제이다.

그렇다면 근손실이 최소로 일어나게 할 경우는 어떤 경우가 되어야 할까?

 

운동기구의 개수(N)이 5, 각 운동기구의 근손실 정도가 1, 2, 3, 4,5 라고 하자.

향단이는 하루 최대 2개의 운동기구를 사용할 수 있으므로, 이중 하나는 제외해야 한다.

 

만약 1을 제외했다고 하면, 2, 3, 4, 5가 남는데,

이렇게 되면 (2,5) (3,4) 혹은 (2,3) (4,5) 혹은 (2,4) (3,5)의 경우가 나오게 되고,

각각의 근손실 값은 7, 9, 8 이 나오게 된다.

((2,3) (4,5)의 경우 각각 근손실은 5, 9가 나오게 되는데, 9가 더 크므로 최소 9의 근손실은 무조건 나오게 되어있다.)

 

그렇다면, 이중 최솟값인 7은 어떻게 나오게 되는 것일까?

답은 간단하다.

각 운동기구의 근손실 정도가 최소가 나오려면, 주어진 값들 중 최대값 + 최소값을 더해 비교해나가면 된다.

이렇게 되면, 최대 + 최대보다 약간 작은 값의 합을 방지해, 더 큰 값이 생기는 것을 막으므로,

위와 같은 방식으로 더해나가는 방식이 가장 합리적이다.

 

두번째로, 만약 주어진 운동기구의 개수가 홀수개라면, 어떤 운동기구 한가지를 빼야하는가?

이것또한 마찬가지이다. 무조건 가장 근손실이 큰 운동기구를 빼야한다.

큰 수는 더할수록 커지고, 작은 수는 그래봤자 작다는 개념을 떠올려보자.

위의 예제에서 1이 아닌 5를 빼게 되면, 1,2,3,4 가 나오므로 어떤 수를 더해도 5를 넘지 않게 된다.

가장 큰 수를 따로 빼주고, 나머지 작은 수들을 가지고 조합 하는 것이 근손실을 최대한 방지하게된다.

 

 

 

3. 소스코드

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

int main() {
	int N;
	long long t[10000];
	long long min = 0;

	cin >> N;

	for (int i = 0; i < N; i++) {
		cin >> t[i];
	}

	// 근손실 정도를 정렬
	sort(t, t + N);

	// 3. 운동기구의 개수가 홀수인 경우
	if (N % 2 == 1) {
		min = t[N - 1];	// 마지막 가장 큰 값을 따로 저장
		N--;

		for (int i = 0; i < N / 2; i++) {
			// 마지막 값을 제외한 최소, 최대값의 합
			long long M = t[i] + t[(N - 1) - i];
			if (M > min) {	// 마지막 값보다 크면
				min = M;	// 최솟값을 초기화
			}
		}
	}

	// 2. 운동기구의 개수가 짝수인 경우
	else {
		for (int i = 0; i < N / 2; i++) {
			// 마지막 값을 제외한 최소, 최대값의 합
			long long M = t[i] + t[(N - 1) - i];
			if (M > min) {	// 마지막 값보다 크면
				min = M;	// 최솟값을 초기화
			}
		}
	}

	cout << min;

	return 0;
}

우선 운동기구의 개수(N)와 각 운동기구의 근손실정도(t[i])를 입력받는다.

이때, 근손실 정도의 범위가 매우 크므로 long long 형을 사용해주었다.

 

주어진 근손실정도를 오름차순으로 정렬 후, (더해주는 것을 용이하게 하기 위함)

1. 운동기구의 개수가 홀수인 경우 와 2. 운동기구의 개수가 짝수인 경우로 나누어

홀수인 경우에는 마지막 값(가장 근손실이 큰 값)을 따로 빼주어 저장 후,

남은 값들중 최대, 최소값을 더해나가며 이를 마지막 값과 비교,

더 큰값이 나오면 초기화 하는 방식으로 근손실값을 구했다.

짝수인 경우에도 홀수인 경우와 마찬가지로 남은 값들 중의 최대, 최소 합을 이용해 근손실 값을 구했다.

 

 

---

그리디 문제를 하나하나 정복해 나가려고 노력중이다..

생각만 잘 하면 어렵지 않을텐데 생각해내는 과정이 참 어려운 것 같다..😥