BOJ - 서강 근육맨

20300 서강 근육맨 : https://www.acmicpc.net/problem/20300

---

Problem

---

Solve

운동기구는 최대 두개까지만 선택할 수 있습니다.
두개의 운동기구를 선택했을때, 두 합의 최대가 최소가 되도록하는 M을 찾아야합니다.

두 합의 크기가 최소가 나오게하기 위해서는 주어진 값에서 작은값과 큰값 두개의 합이 두 합을 구하였을때 나올 수 있는 최소의 합이 됩니다.

주어진 운동기구의 개수가 짝수인 경우, 가장작은값과 가장큰값을 시작으로 두 합을 구해가며 그 다음 작은값과 큰 값의 합을 비교하여 그 값중 가장 큰 값을 찾아주어야합니다.

그런데 주어진 개수가 홀수라면, 가장 작은 값과 가장 큰값이 아닌 가장작은 값과 가장 큰값보다 다음으로 큰 값의 합을 구해야합니다.
1 2 3 4 100이 주어진 경우 1과 100의 합보다, 1과 4의 합이 최소의 M을 구할수 있기 때문입니다.

즉, 두 수의 합이 작게 나올 수 있는 값 중 가장 큰 값을 구해야합니다.

---

Code

public class 서강근육맨 {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int N = Integer.parseInt(br.readLine());
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		long[] loss = new long[N];
		for (int i = 0; i < N; i++) {
			loss[i] = Long.parseLong(st.nextToken());
		}

		Arrays.sort(loss);

		int start = 0;
		int end = N - 1;
		if (N % 2 != 0)
			end = N - 2;

		long max = getMaxLoss(start, end, loss);
		if (N % 2 != 0) max = Math.max(max, loss[N - 1]);

		bw.write(String.valueOf(max));
		bw.flush();
		bw.close();
	}

	static long getMaxLoss(int start, int end, long[] loss) {
		long max = 0;

		while (start < end) {
			max = Math.max(max, (loss[start] + loss[end]));
			start++;
			end--;
		}

		return max;
	}
}

---

Result

---

Reference