[백준 11497] 통나무 건너뛰기 [Java]

문제

http://boj.ma/11497

11497번: 통나무 건너뛰기

 

---

풀이

문제 요약

N개의 통나무를 원형으로 놓았을 때 인접한 통나무의 최대 높이차가 최소가 되도록 배치하자.

아이디어

통나무를 단순히 정렬하면 1, N 번 통나무의 높이차로 인해, 좋은 배치가 될 수 없다.

우선 오름차순으로 정렬 후, 작은 요소부터 0번 인덱스의 양 옆에 번갈아가며 배치하면 된다. 번갈아 가는 순서는 동일하게 반복만 된다면 왼쪽/오른쪽 중 아무 방향으로 먼저 놓아도 된다.

			// Solve
			Arrays.sort(A);
			int[] B = new int[N];
			for (int i = 0; i < N; ++i) {
				B[i % 2 == 0 ? i / 2 : N - (i / 2) - 1] = A[i];
			}
			
			int maxDiff = B[N - 1] - B[0];
			for (int i = 1; i < N; ++i) {
				maxDiff = Math.max(maxDiff, Math.abs(B[i] - B[i - 1]));
			}

풀이 시간

10분

---

소스코드

https://github.com/rogi-rogi/problem-solving/blob/main/baekjoon-online-judge/easy/11497.java

problem-solving/baekjoon-online-judge/easy/11497.java at main · rogi-rogi/problem-solving