[C++] 11497번: 통나무 건너뛰기

링크

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

11497번: 통나무 건너뛰기

문제

남규는 통나무를 세워 놓고 건너뛰기를 좋아한다. 그래서 N개의 통나무를 원형으로 세워 놓고 뛰어놀려고 한다. 남규는 원형으로 인접한 옆 통나무로 건너뛰는데, 이때 각 인접한 통나무의 높이 차가 최소가 되게 하려 한다.

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정된다. 높이가 {2, 4, 5, 7, 9}인 통나무들을 세우려 한다고 가정하자. 이를 [2, 9, 7, 4, 5]의 순서로 세웠다면, 가장 첫 통나무와 가장 마지막 통나무 역시 인접해 있다. 즉, 높이가 2인 것과 높이가 5인 것도 서로 인접해 있다. 배열 [2, 9, 7, 4, 5]의 난이도는 |2-9| = 7이다. 우리는 더 나은 배열 [2, 5, 9, 7, 4]를 만들 수 있으며 이 배열의 난이도는 |5-9| = 4이다. 이 배열보다 난이도가 낮은 배열은 만들 수 없으므로 이 배열이 남규가 찾는 답이 된다.

입출력 예제

입력

입력은 T개의 테스트 케이스로 이루어져 있다. 첫 줄에 T가 주어진다.

이어지는 각 줄마다 첫 줄에 통나무의 개수를 나타내는 정수 N(5 ≤ N ≤ 10,000), 둘째 줄에 각 통나무의 높이를 나타내는 정수 Li가 주어진다. (1 ≤ Li ≤ 100,000)

출력

각 테스트 케이스마다 한 줄에 주어진 통나무들로 만들 수 있는 최소 난이도를 출력하시오.

예제 입력 1 복사

3
7
13 10 12 11 10 11 12
5
2 4 5 7 9
8
6 6 6 6 6 6 6 6

예제 출력 1 복사

1
4
0

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <stack>

using namespace std;

int main(void)
{
	cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	int t;
	cin >> t;

	while (t--)
	{
		int n;
		cin >> n;

		vector<int> wood(n);

		for (int i = 0; i < n; i++)
			cin >> wood[i];

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

		int result = 0;

		for (int i = 0; i < n - 2; i++)
			result = max(wood[i + 2] - wood[i], result);

		cout << result << "\n";
	}
}

풀이

• 그리디 알고리즘을 이용해서 해결했다.
  
  

오름차순으로 정렬된 수 들이 있으면 다음과 같은 그래프를 이루는 배치가 가장 난이도가 작은 배치일 것이다

이를 위해서 오름차순으로 정렬된 수를 가장 작은 수 부터 하나씩 양쪽으로 번갈아가며 배치하면

자기 양 옆으로는 가장 편차가 작은 수들로 이루어져 있을 것이다.

 

참고로 처음 인덱스와 마지막 인덱스는 서로 이어져 있다고 판단한다!

 

양쪽으로 번갈아 가면서 새로 배치하는 것 보다 좋은 방법이 있는데

1  2  3  4  5

빨간색으로 표시 해놓은 것 처럼 인덱스를 두번 건너뛸 때 마다 인접한 인덱스가 나타난다.

현재 인덱스를 i라고 하면 (i+2 - i) 가 인접한 수 끼리의 난이도를 비교하는 식이 될 것이고
이를 max 함수를 이용해 최대값을 뽑아내면 된다.

위의 수를 가장 난이도가 작게 배치하자면

1  3  5  4  2

이렇게 바꿀 수 있고

바꾸기 전 i와 i+2 의 숫자가 서로 인접하게 됐음을 알 수 있다.

result = max(wood[i + 2] - wood[i], result);

이 코드를 이용해서 난이도의 최대값을 뽑아내면

1  3  5  4  2
1  3  5  4  2

다음과 같은 경우의 난이도를 뽑아낼 수 없게 되는데

양쪽 끝 인덱스와 홀수/짝수 인덱스의 경계 같은 경우는
처음과 끝 인덱스는 오름차순 정렬에서 처음과 두번째 수 이고,
홀수/짝수의 경계는 오름차순 정렬에서 마지막과 마지막의 한 칸 이전의 수 이다!

이는 어차피 i 와 i + 1 의 관계라
오름차순으로 정렬 된 상태에서의
i 와 i + 2 의 관계보다 난이도가 작을 수 밖에 없기 때문에 계산할 필요가 없다!