[C++][BOJ 11497/통나무 건너뛰기] 그리디, 정렬

통나무 건너뛰기

 

통나무 건너뛰기의 난이도는 인접한 두 통나무 간의 높이의 차의 최댓값으로 결정

주어진 통나무들로 만들 수 있는 최소 난이도를 구하는 문제이다.

 

 

문제 풀이

결국 난이도가 최소가 되도록 배치를 하게 될것이다.

[13 10 12 11 10 11 12] 이 예제로 생각해보자.

정렬한 결과

13	10	12	11	10	11	12
10	10	11	11	12	12	13
10	10	11	11	12	12	13

이 상태에서 난이도가 최소가 되도록 배치한다면 결국 정렬 후에 차이가 가장 적게 나는 것을 양옆에 배치할것이다.

10 기준으로 양 옆에는 10,11이 오게 배치될 것이다.

12 기준으로는 양 옆에 12 13가 오게 배치될 것이다.

이렇에 모든 수에 양옆에 이런식으로 배치될 것이다. 

정렬 후 현재 위치에서 2칸 떨어진 곳의 수의 차이 중 최대값을 고르면 된다.

10

10

11

11

12

12

13

 11 을 기준으로 10,11 이렇게 양옆으로 계산하지 않는 이유는 배열의 맨끝과 맨앞도 서로 인접하다 보기 때문

 

 

 

소스코드

#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	
	int T;
	cin >>T;
	while(T--){
		int N,ans=0;
		cin >> N;
		int log_arr[N];
		for(int i = 0 ;i < N;i++) cin>> log_arr[i];

		sort(log_arr,log_arr+N);
		
		for(int i = 0 ; i <N-2 ;i++){
			ans = max(log_arr[i+2]-log_arr[i], ans);
		}
		cout<<ans<<"\n";
	}
	
}