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

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. 양 옆에 존재하는 통나무의 높이 차이 중 최소값이 되는 조합을 찾는 문제이다.  완전탐색으로 접근 할 경우 시간초과가 발생할 것 같아 다음과 같은 방식으로 접근하였다.

 

2. 우선순위 큐를 이용하여 오름차순으로 정렬 한 후 양쪽  사이드부터 채워 나간다면 균등하게 최소 레벨을 구 할 수 있다고 판단하였다.

 

3. {1, 2, 3, 4, 5} 가 있으면, 1, 3, 5, 4, 2로 구성이 되어 난이도 2가 가장 낮은 구간이 된다. 

 

4. 마지막 구간과 처음 구간은 연결되어 있으므로 꼭 체크를 해야한다.

 

소스코드

#include<stdio.h>
#include<queue>
#include<algorithm>
#include<functional>
using namespace std;
int map[10000];
int main()
{
	int tc;
	scanf("%d", &tc);
	int N;
	for (int i = 0; i < tc; i++) {
		scanf("%d", &N);
		priority_queue<int, vector<int>, greater<int>> pq;
		for (int i = 0; i < N; i++) {
			int n;
			scanf("%d", &n);
			pq.push(n);
		}
		int left = 0, right = N - 1;
		for (int i = 0; i < N; i++) {
			int num = pq.top(); pq.pop();
			if (i % 2 == 0) {
				map[left] = num;
				left++;
			}
			else {
				map[right] = num;
				right--;
			}
		}
		int answer = abs(map[0] - map[N-1]);
		for (int i = 0; i < N - 1; i++) {
			int diff = abs(map[i] - map[i + 1]);
			if (answer < diff) {
				answer = diff;
			}
		}
		printf("%d\n", answer);
	}
}

결과