취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 11497번 문제인 통나무 건너뛰기이다.
문제는 아래 링크를 확인하자.

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

다양한 높이를 가진 통나무 N개를 원형으로 늘어놓을 때, "인접한 통나무의 높이 차의 최댓값"을 최소화하는 문제이다.

가지고있는 통나무들을 높이를 기준으로 오름차순으로 나열한 높이들을 h1, h2, ..., hn이라고 하자.

이때, 문제에서 요구하는 원형 통나무 배치는 높이 h1 통나무에서 hn 통나무까지 이동했다가 다시 h1으로 돌아가면서 아직 밟지 않은 통나무들만을 이용하는 하나의 경로로 생각할 수 있다. 이를 h1과 hn 사이의 두 구간으로 쪼개면, h1을 시작점으로, h2를 끝점으로 하면서 시작점과 끝점이 겹치지 않고 모든 노드가 두 경로중 하나에 들어가있는 두 개의 경로를 생각할 수 있다. 이 두 경로에서 만들어지는 각각의 "인접한 통나무들의 높이 차의 최댓값"을 최소화하는 것이 문제이다.

조금 생각을 해보면, h1과 h2, h(n-1)과 hn 사이를 제외하면 두 개의 인접한 높이의 통나무는 서로 다른 경로에 나눠서 넣어주는 것이 같은 경로에 들어있을 때보다 통나무 높이차의 최댓값이 커지지 않을 것임을 알 수 있다.

따라서, 각 경로에 통나무를 크기순으로 하나씩 넣는 것으로 최적의 경로를 구할 수 있다. 이 상황에서의 각 경로의 인접한 통나무 높이 차이의 최솟값을 계산하여 출력하자.

아래는 제출한 소스코드이다.

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

int arr[10000];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int T; cin >> T;
	while (T--) {
		int N; cin >> N;
		for (int i = 0; i < N; i++) cin >> arr[i];
		sort(arr, arr + N);
		int ans = 0;
		for (int i = 2; i < N; i++) ans = max(ans, arr[i] - arr[i - 2]);

		cout << ans << '\n';
	}
}