[ 11497 ] 통나무 건너뛰기 - 그리디

< 그리디 > - < 실버 1 >

 

[ 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)

:: 출력

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

---

- try 1 

: 가장 큰 값과 그 앞, 그 앞앞 값만 비교하면 된다고 생각해서 그렇게 짰음

주어진 예시는 다 통과하는데 틀림 ,,

 

- try 2 

: 솔루션 참고해서 코드 고쳤는데 반복문 문자 헷갈려서 틀림 ,, 멍청

 

 

  아이디어  

풀이 찾아보니까

가장 큰값을 기준으로 양쪽으로 번갈아가며 값을 붙이며 배열을 만든다는 생각은 똑같은데

이걸 일반화 함

 

ex) 

 

2, 4, 5, 7, 9 -> 0, 1, 2, 3, 4 로 인덱스화 해서 배열을 만들면 

최소 난이도가 나오는 배열은 아래와 같음

 

0 2 4 3 1

2 5 9 7 4

 

이때 각 항은 인덱스가 2씩 차이나게 됨

인덱스가 1씩 차이나게 배열을 만드는 경우는 첫항과 마지막항이 너무 큰 차이가 나기때문에 답이 될 수 없음

 

결론적으로 최소 난이도를 가지는 배열은 각항의 인덱스가 2 이하로 차이나는 배열이 된다 !

통나무의 높이를 저장해둔 벡터를 처음부터 탐색하면서 인덱스 2 차이 나는 값과 차이를 비교 해줌

		for (int x = 0; x <= k - 3; x++) {
			int v = abs(nums[x] - nums[x+2]);
			if (v > ans) {
				ans = v;
			}
		}

 

 

  정답  코드  

#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;


int main() {

	int n = 0;
	cin >> n;

	vector<int> answers;

	for (int i = 0; i < n; i++) {
		int k = 0;

		vector<int> nums;

		cin >> k;

		for (int j = 0; j < k; j++) {
			int h = 0;
			cin >> h;
			nums.push_back(h);
		}

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

		int ans = 0;

		for (int x = 0; x <= k - 3; x++) {
			int v = abs(nums[x] - nums[x+2]);
			if (v > ans) {
				ans = v;
			}
		}

		answers.push_back(ans);
	}

	for (int i = 0; i < answers.size(); i++) {
		printf("%d\n", answers[i]);
	}

	return 0;
}